洛谷 P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量

题目传送门

解题思路:

先求强联通分量,缩点,然后统计新图中有几个点出度为0,如果大于1个,则说明这不是一个连通图,答案即为0.否则入度为0的那个强连通分量的点数即为答案

AC代码:

 #include<iostream>

 #include<cstdio>

 #include<stack>

 #include<set>

 using namespace std;

 int daan,n,m,head[],tot;

 int dfn[],low[],sum,rp;

 int belong[],_head[],num[];

 bool vis[];

 struct kk{

     int to,next;

 }e[],a[];

 stack<int> s;

 set<int> ans[];

 inline void add(int x,int y) {

     e[++tot].to = y;

     e[tot].next = head[x];

     head[x] = tot;

 }

 inline void tarjan(int x) {

     dfn[x] = low[x] = ++sum;

     int v;

     s.push(x);

     vis[x] = ;

     for(int i = head[x];i != ; i = e[i].next) {

         v = e[i].to;

         if(!dfn[v]) {

             tarjan(v);

             low[x] = min(low[x],low[v]);

         }

         else if(vis[x])

             low[x] = min(low[x],dfn[v]);

     }

     if(dfn[x] == low[x]) {

         rp++;

         do {

             v = s.top();

             s.pop();

             belong[v] = rp;

             num[rp]++;

             vis[x] = false;

         }

         while(v != x);

     }

 }

 inline void _add(int x,int y) {

     a[++tot].to = y;

     a[tot].next = _head[x];

     _head[x] = tot;

 }

 inline void findin() {

     for(int i = ;i <= rp; i++)

         for(int j = _head[i];j != ; j = a[j].next) {

             int o = a[j].to;

             ans[i].insert(o);

         }

 }

 int main() {

     scanf("%d%d",&n,&m);

     for(int i = ;i <= m; i++) {

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y);

     }

     for(int i = ;i <= n; i++)

         if(!dfn[i])    //求强连通分量

             tarjan(i);

     tot = ;

     for(int i = ;i <= n; i++)//构建新图,其实没啥必要

         for(int j = head[i];j != ; j = e[j].next)

             if(belong[i] != belong[e[j].to])

                 _add(belong[i],belong[e[j].to]);

     findin();

     for(int i = ;i <= rp; i++)//找入度为0的点

         if(ans[i].size() == ) {

             if(daan != )  {

                 printf("");

                 return ;

             }

             daan = i;

         }

     printf("%d",num[daan]);

     return ;

 } 

第一次的做法,用了set,较麻烦

 #include<iostream>

 #include<cstdio>

 #include<stack>

 #include<set>

 using namespace std;

 int daan,n,m,head[],tot;

 int _out[],dfn[],low[];

 int sum,rp,belong[];

 int _head[],num[];

 bool vis[];

 struct kk{

     int to,next;

 }e[],a[];

 stack<int> s;

 inline void add(int x,int y) {

     e[++tot].to = y;

     e[tot].next = head[x];

     head[x] = tot;

 }

 inline void tarjan(int x) {

     dfn[x] = low[x] = ++sum;

     int v;

     s.push(x);

     vis[x] = ;

     for(int i = head[x];i != ; i = e[i].next) {

         v = e[i].to;

         if(!dfn[v]) {

             tarjan(v);

             low[x] = min(low[x],low[v]);

         }

         else if(vis[x])

             low[x] = min(low[x],dfn[v]);

     }

     if(dfn[x] == low[x]) {

         rp++;

         do {

             v = s.top();

             s.pop();

             belong[v] = rp;

             num[rp]++;

             vis[x] = false;

         }

         while(v != x);

     }

 }

 inline void _add(int x,int y) {

     a[++tot].to = y;

     a[tot].next = _head[x];

     _head[x] = tot;

 }

 int main() {

     scanf("%d%d",&n,&m);

     for(int i = ;i <= m; i++) {

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y);

     }

     for(int i = ;i <= n; i++)

         if(!dfn[i])

             tarjan(i);

     tot = ;

     for(int i = ;i <= n; i++)

         for(int j = head[i];j != ; j = e[j].next)

             if(belong[i] != belong[e[j].to])

                 _out[belong[i]]++;

     for(int i = ;i <= rp; i++)

         if(_out[i] == ) {

             if(daan != )  {

                 printf("");

                 return ;

             }

             daan = i;

         }

     printf("%d",num[daan]);

     return ;

 } 

改进后的代码,发现不用set,比较精简