并查集+缩块


缩块的时候判断块中的点的数量，
对于 a ，b
a与b不在同一并查集里  zero
a与b在同一并查集里时：
a，b不在同一块中, one
a，b在同一块中时：
块中点数大于2，two
否则 one

一个u打成v让我找了一个晚上的错。。。。。。

Financial Crisis

Because of the financial crisis, a large number of enterprises go bankrupt. In addition to this, other enterprises, which have trade relation with the bankrup enterprises, are also faced with closing down. Owing to the market collapse, profit decline and funding chain intense, the debt-ridden entrepreneurs
have to turn to the enterprise with stably developing for help.

Nowadays, there exist a complex net of financial trade relationship between enterprises. So if one of enterprises on the same financial chain is faced with bankrupt, leading to cashflow‘s obstruction, the other enterprises related with it will be influenced as well. At the moment, the foresight entrepreneurs are expected the safer cooperation between enterprises. In this sense, they want to know how many financial chains between some pairs of enterprises are independent with each other. The indepence is defined that if there exist two roads which are made up of enterprises(Vertexs) and their financial trade relations(Edge) has the common start point S and end point T, and expect S and T, none of other enterprise in two chains is included in these two roads at the same time. So that if one of enterpirse bankrupt in one of road, the other will not be obstructed.

Now there are N enterprises, and have M pair of financial trade relations between them, the relations are Mutual. They need to ask about Q pairs of enterprises‘ safety situations. When two enterprises have two or more independent financial chains, we say they are safe enough, you needn‘t provide exact answers.

3 1 2
0 1
0 2
1 0
4 4 2
0 1
0 2
1 2
2 3
1 2
1 3
0 0 0

Case 1:
zero
one
Case 2:
two or more
one

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

/***********build*************/
const int maxV=5500;
const int maxE=11000;

int N,M,Q;

struct Edge
{
    int to,next;
}edge[maxE*2];

int Adj[maxV],Size;

void init()
{
    Size=0; memset(Adj,-1,sizeof(Adj));
}

void Add_Edge(int u,int v)
{
    edge[Size].to=v;
    edge[Size].next=Adj[u];
    Adj[u]=Size++;
}

/************tarjan****************/

int DFN[maxV],Stack[maxV],InStack[maxV],Low[maxV],Index,be,top;
int numblock[maxV];

vector<int> Belong[maxV];

void tarjan(int u,int fa)
{
    int v;
    DFN[u]=Low[u]=++Index;
    Stack[top++]=u;InStack[u]=1;

    for(int i=Adj[u];~i;i=edge[i].next)
    {
        v=edge[i].to;
        if(v==fa) continue;
        if(DFN[v]==0)
        {
            tarjan(v,u);
            Low[u]=min(Low[u],Low[v]);

            if(Low[v]>=DFN[u])
            {
                be++;
                do
                {
                    Belong[Stack[--top]].push_back(be);
                    InStack[Stack[top]]=0;
                    numblock[be]++;
                }while(Stack[top]!=v);
                Belong[u].push_back(be);
                numblock[be]++;
            }
        }
        else Low[u]=min(Low[u],DFN[v]);
    }
}
void dscc_solve()
{
    memset(DFN,0,sizeof(DFN));
    memset(InStack,0,sizeof(InStack));
    memset(Low,0,sizeof(Low));
    memset(numblock,0,sizeof(numblock));
    for(int i=0;i<N;i++) Belong[i].clear();
    Index=top=be=0;

    for(int i=0;i<N;i++)
        if(DFN[i]==0) tarjan(i,i);
}

/************disjoin**********************/

int fa[maxV];

void un_init()
{
    for(int i=0;i<=N;i++) fa[i]=i;
}

int Find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a==b) return ;
    fa[a]=b;
}


int main()
{
    int cas=1;
    while(scanf("%d%d%d",&N,&M,&Q)!=EOF)
    {
        if(N==0&&M==0&&Q==0) break;
        init(); un_init();
        for(int i=0;i<M;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Add_Edge(a,b);
            Add_Edge(b,a);
            Union(a,b);
        }
        dscc_solve();
        printf("Case %d:\n",cas++);
        while(Q--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(Find(a)!=Find(b))
            {
                puts("zero");
                continue;
            }
            else
            {
                bool flag=false;
                int lt=-1;
                for(int i=0,sa=Belong[a].size();i<sa;i++)
                {
                    for(int j=0,sb=Belong[b].size();j<sb;j++)
                    {
                        if(Belong[a][i]==Belong[b][j])
                        {
                            lt=Belong[a][i];
                            flag=true; break;
                        }
                    }
                    if(flag) break;
                }
                if(flag==false) puts("one");
                else
                {
                    if(numblock[lt]<=2) puts("one");
                    else puts("two or more");
                }
            }
        }
    }
    return 0;
}

HDOJ 3479 Financial Crisis,布布扣,bubuko.com

HDOJ 3479 Financial Crisis

原文：http://blog.csdn.net/ck_boss/article/details/23557707