[집합 판단 연통 무 환 도]


HDU - 1272 | HDU - 1325 소희 의 미로 | Is it a tree?
http://acm.hdu.edu.cn/showproblem.php?pid=1272
http://acm.hdu.edu.cn/showproblem.php?pid=1325
그림 이 나무 (연결, 고리 없 음) 인지 판단 하 는 두 가지 관건:

순환 도로 가 존재 하지 않 는 다 (방향 그림 이 있 고 순환 도로 가 존재 하지 않 는 다 는 것 은 강 한 연결 서브 맵 이 존재 하지 않 는 다 는 것 을 의미한다)

변 수 를 하나 더 하 는 것 이 정점 과 같은 규칙 (중 변 과 자신 을 가리 키 는 변 을 고려 하지 않 음) - 근 유일

사실 나 는 이 두 문제 의 차이 가 많 지 않다 고 생각한다. 단지 1325 개의 변 을 방향 이 있 는 변 으로 바 꾸 었 을 뿐이다. 나 는 ok 아, 별 차이 가 없다 고 생각한다. 예 를 들 어 1 - 2, 2 - 3, 4 - 2 이렇게 하면 너 는 어떠한 최적화 결과 도 넣 지 않 으 면 3 을 뿌리 로 나 무 를 얻 을 수 있다 (중대 형). 분명히 모인 것 이 아니 라 발산 한 것 이다. 바로 근 의 입 도 는 0 이다.그래서 1325 에 입 도 를 하나 더 해서 판단 하면 돼 요.
일단 간단 한 1272.

#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 1e4;
int pre[maxn],s[maxn],vis[maxn];
int pcnt,ecnt,retflag;

void init()
{
    for(int i = 0;i < maxn;i++)
    {
        pre[i] = i;
        s[i] = 1;
        vis[i] = 0;
    }
    pcnt = ecnt = 0;
    retflag = 1;
}
int Find(int x)
{
    while(x != pre[x])
    {
        pre[x] = pre[pre[x]];
        x = pre[x];
    }
    return x;
}
void join(int a,int b)
{
    int u = Find(a);
    int v = Find(b);
    if(u == v)
    {
        retflag = 0;
    }
    else
    {
        if(!vis[a] && u == a)vis[a] = 1,pcnt++;
        if(!vis[b] && v == b)vis[b] = 1,pcnt++;
        ecnt++;
        if(s[u] > s[v])
        {
            pre[v] = u;
            s[u] += s[v];
        }
        else
        {
            pre[u] = v;
            s[v] += s[u];
        }
    }
}
int main()
{
    int a,b;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a == b && a == -1)break;

        if(a == b && a == 0)
        {
            if(ecnt == 0)printf("Yes
");
            else if(!retflag || ecnt + 1 != pcnt)
            {
                printf("No
");
            }
            else printf("Yes
");
            init();
        }
        else if(!retflag)
        {
            continue;
        }
        else
        {
            join(a,b);
        }
    }
    return 0;
}

 기본적으로 대부분이 템 플 릿 을 끼 워 넣 어야 하기 때문에 따로 말 하지 않 습 니 다. 경로 압축 과 균형 트 리 가 있어 야 하지만 시간 이 느 립 니 다. 데이터 의 범 위 를 모 르 기 때문에 매번 업데이트 횟수 가 GG 가 많 고 1325 는 약간 바 뀌 었 습 니 다.
1325

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e6;
int pre[maxn],vis[maxn],in[maxn];
int pcnt,ecnt,retflag;

void init(int n = 1e5 + 1e4)
{
    for(int i = 0;i <= n;i++)
    {
        pre[i] = i;
        vis[i] = 0;
        in[i] = 0;
    }
    pcnt = ecnt = 0;
    retflag = 1;
}
int Find(int x)
{
    while(x != pre[x])
    {
        pre[x] = pre[pre[x]];
        x = pre[x];
    }
    return x;
}
void join(int a,int b)
{
    int u = Find(a);
    int v = Find(b);
    if(u == v)
    {
        if(!vis[u])vis[u] = 1,pcnt++;
        retflag = 0;
    }
    else
    {
        if(!vis[a] && u == a)vis[a] = 1,pcnt++;
        if(!vis[b] && v == b)vis[b] = 1,pcnt++;
        ecnt++;
        if(++in[b] > 1)retflag = 0;
        pre[u] = v;
    }
}
int main()
{
    int a,b,cas = 1;
    int retn = 0;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a < 0 || b < 0)break;
        retn = max(retn,max(a,b));
        if(a == b && a == 0)
        {
            if(ecnt == 0 && pcnt == 0)printf("Case %d is a tree.
",cas++);
            else if(!retflag || ecnt + 1 != pcnt)
            {
                printf("Case %d is not a tree.
",cas++);
            }
            else printf("Case %d is a tree.
",cas++);
            init(retn);
        }
        else if(!retflag)
        {
            continue;
        }
        else
        {
            join(a,b);
        }
    }
    return 0;
}

 1325 이 문 제 는 사람 을 함정 에 빠 뜨리 는 곳 이 하나 있 는데 바로 끝 에 a 또는 b 라 고 판단 하 는 것 이다. 하 나 는 마이너스 이다. 내 가 왜 항상 re 라 고 했 는데 원래 a [- 2] 를 방 문 했 구나.
다른 건 다 좋아요.