POJ2762 UV

题意：n个山洞，对于每两个山洞s,e，都满足s可以到达e或者e可以到达s，则输出Yes,否则输出No。

————————————————————————————————————————

第一个缩点的题目，道理早就明白，从来没写过。

首先，有些点是可以互通的，在强连通分量里面，所以强连通分量缩点。

方法：

1、tarjan，求出各个点分别属于哪一个分量。

2、读取所有的边，判断边的两点是否属于不同分量，不同则在两个分量间建边。

然后，只能有一个点入读为了0，所有点初读都不大于1，输出“yes”,否则输出"no".

————————————————————————————————————————

  1 //utovorvtou
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<stack>
  7 
  8 using namespace std;
  9 const int maxm=6010;
 10 const int maxn=1010;
 11 int T,n,m;
 12 struct edge
 13 {
 14     int u,v,next;
 15 }e[maxm],ee[maxm];
 16 int head[maxn],js,headd[maxn],jss;
 17 bool ins[maxn];
 18 int visx,sshu;
 19 int dfsn[maxn],low[maxn],belong[maxn];
 20 int rudu[maxn],chudu[maxn];
 21 stack<int>st;
 22 
 23 void init()
 24 {
 25     memset(head,0,sizeof(head));
 26     js=0;
 27     memset(headd,0,sizeof(headd));
 28     jss=0;
 29     memset(ins,0,sizeof(ins));
 30     while(!st.empty())st.pop();
 31     visx=0;
 32     sshu=0;
 33     memset(dfsn,-1,sizeof(dfsn));
 34     memset(low,-1,sizeof(low));
 35     memset(rudu,0,sizeof(rudu));
 36     memset(chudu,0,sizeof(chudu));
 37 }
 38 void addage(int u,int v,edge e[],int &js,int head[])
 39 {
 40     e[++js].u=u;e[js].v=v;
 41     e[js].next=head[u];head[u]=js;
 42 }
 43 void tarjan(int u)
 44 {
 45     dfsn[u]=low[u]=++visx;
 46     ins[u]=1;
 47     st.push(u);
 48     for(int j=head[u];j;j=e[j].next)
 49     {
 50         int v=e[j].v;
 51         if(dfsn[v]==-1)
 52         {
 53             tarjan(v);
 54             if(low[v]<low[u])low[u]=low[v];
 55         }
 56         else if(ins[v] && low[u]>dfsn[v])low[u]=dfsn[v];
 57     }
 58     int j;
 59     if(low[u]==dfsn[u])
 60     {
 61         sshu++;
 62         do
 63         {
 64             j=st.top();
 65             st.pop();
 66             ins[j]=0;
 67             belong[j]=sshu;
 68         }while(j!=u);
 69     }
 70 }
 71 stack<int>s;
 72 bool topo()
 73 {
 74     int tp=0,maxt=0;
 75     for(int i=1;i<=sshu;i++)
 76     {
 77         if(rudu[i]==0)
 78         {
 79             tp++;
 80             
 81         }
 82         if(chudu[i]>maxt)maxt=chudu[i];
 83         
 84     }
 85     if(tp>1)return 0;
 86     if(maxt>1)return 0;
 87     return 1;
 88 }
 89 int main()
 90 {
 91     cin>>T;
 92     while(T--)
 93     {
 94         scanf("%d%d",&n,&m);
 95         init();
 96         for(int u,v,i=0;i<m;i++)
 97         {
 98             scanf("%d%d",& u,&v);
 99             addage(u,v,e,js,head);
100         }
101         for(int i=1;i<=n;i++)
102         {
103             if(dfsn[i]==-1)tarjan(i);
104         }
105         for(int i=1;i<=js;i++)
106         {
107             int u=e[i].u,v=e[i].v;
108             if(belong[u]!=belong[v])
109             {
110                 addage(belong[u],belong[v],ee,jss,headd);
111                 rudu[belong[v]]++;chudu[belong[u]]++;
112             }
113         }
114         if(topo()==1)printf("Yes\n");else printf("No\n");
115     }
116     return 0;
117 }

View Code