当前位置：首页 > news >正文

poj 2186

news 来源：原创 2024/5/7 12:34:47

poj 2186
tarjan缩点板子题
缩完点之后是有向无环图，要想其他点都能到达，那么它的出度为0，不然随意连就会出现环，如果出度为0的点的个数不是1，肯定就凉了。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<ctime>
  7 #include<set>
  8 #include<map>
  9 #include<stack>
 10 #include<cstring>
 11 #define inf 2147483647
 12 #define ls rt<<1
 13 #define rs rt<<1|1
 14 #define lson ls,nl,mid,l,r
 15 #define rson rs,mid+1,nr,l,r
 16 #define N 100010
 17 #define For(i,a,b) for(int i=a;i<=b;i++)
 18 #define p(a) putchar(a)
 19 #define g() getchar()
 20 
 21 using namespace std;
 22 int n,m,x,y,now;
 23 int dfn[10010],low[10010],ans[10010];
 24 int cnt,col,c[10010],d[10010];
 25 bool vis[10010];
 26 struct node{
 27     int n;
 28     node *next;
 29 }*e[500100];
 30 
 31 stack<int>s;
 32 
 33 void in(int &x){
 34     int y=1;
 35     char c=g();x=0;
 36     while(c<'0'||c>'9'){
 37         if(c=='-')y=-1;
 38         c=g();
 39     }
 40     while(c<='9'&&c>='0'){
 41         x=(x<<1)+(x<<3)+c-'0';c=g();
 42     }
 43     x*=y;
 44 }
 45 void o(int x){
 46     if(x<0){
 47         p('-');
 48         x=-x;
 49     }
 50     if(x>9)o(x/10);
 51     p(x%10+'0');
 52 }
 53 
 54 void push(int x,int y){
 55     node *p;
 56     p=new node();
 57     p->n=y;
 58     if(e[x]==NULL)
 59         e[x]=p;
 60     else{
 61         p->next=e[x]->next;
 62         e[x]->next=p;
 63     }
 64 }
 65 
 66 void tarjan(int x){
 67     dfn[x]=low[x]=++cnt;
 68     vis[x]=true;
 69     s.push(x);
 70     for(node *i=e[x];i;i=i->next){
 71         if(!dfn[i->n]){
 72             tarjan(i->n);
 73             low[x]=min(low[x],low[i->n]);
 74         }
 75         else
 76             if(vis[i->n])
 77                 low[x]=min(low[x],dfn[i->n]);
 78     }
 79 
 80     if(low[x]==dfn[x]){
 81         col++;
 82         do{
 83             ans[col]++;
 84             now=s.top();
 85             c[now]=col;
 86             s.pop();
 87             vis[now]=true;
 88         }while(x!=now);
 89     }
 90 }
 91 
 92 void dfs(int x){
 93     vis[x]=true;
 94     for(node *i=e[x];i;i=i->next){
 95         if(!vis[i->n]){
 96             if(c[i->n]!=c[x])
 97                 d[c[x]]++;
 98             dfs(i->n);
 99         }
100     }
101 }
102 
103 int main(){
104     in(n);in(m);
105     For(i,1,m){
106         in(x);in(y);
107         push(x,y);
108     }
109     For(i,1,n)
110         if(!dfn[i])
111             tarjan(i);
112 
113     For(i,1,n)vis[i]=false;    
114 
115     For(i,1,n)
116         if(!vis[i])
117             dfs(i);
118     cnt=0;
119     For(i,1,col){
120         if(d[i]==0){
121             x=i;
122             cnt++;
123         }
124         //o(d[i]);p('\n');
125     }
126     if(cnt==1)
127         o(ans[x]);
128     else
129         o(0);
130     return 0;
131 }