根据题意求的是出度为0的强连通分量的点的个数，这与POJ 2186有非常相似的地方，因为入度不方便统计，所以直接统计出度，出度为0即为正确答案。

思路：

利用Tarjan求强连通分量，并求出入度为0的强连通分量。

另外，题目要求输出从小到大，而我们知道Tarjan求强连通分量的顺序就是从小到大，所以不需要记录、排序然后输出。

CODE：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>


using 
namespace std;

#define MAXN 10010


#define MAXM 100010

struct Edge

{

    
int v, next;

}edge[MAXM];

int first[MAXN], stack[MAXN], ins[MAXN], dfn[MAXN], low[MAXN];


int belong[MAXM];


int outd[MAXN];

int n, m;


int cnt;


int scnt, top, tot;

void init()

{

    cnt = 
0;

    scnt = top = tot = 
0;

    memset(first, -
1, 
sizeof(first));

    memset(ins, 
0, 
sizeof(ins));

    memset(dfn, 
0, 
sizeof(dfn));

}

void read_graph(
int u, 
int v)

{

    edge[cnt].v = v;

    edge[cnt].next = first[u];

    first[u] = cnt++;

}

void dfs(
int u)

{

    
int t;

    low[u] = dfn[u] = ++tot;

    ins[u] = 
1;

    stack[top++] = u;

    
for(
int e = first[u]; e != -
1; e = edge[e].next)

    {

        
int v = edge[e].v;

        
if(!dfn[v])

        {

            dfs(v);

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

        }

        
else 
if(ins[v])

        {

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

        }

    }

    
if(low[u] == dfn[u])

    {

        scnt++;

        
do

        {

            t = stack[--top];

            ins[t] = 
0;

            belong[t] = scnt;

        }
while(t != u);

    }

}

void Tarjan()

{

    
for(
int v = 
1; v <= n; v++) 
if(!dfn[v])

        dfs(v);

}

void solve()

{

    Tarjan();

    memset(outd, 
0, 
sizeof(outd));

    
for(
int u = 
1; u <= n; u++) 
//
n个顶点 

    {

        
for(
int e = first[u]; e != -
1; e = edge[e].next)

        {

            
int v = edge[e].v;

            
if(belong[u] != belong[v]) outd[belong[u]]++;

        }

    }

    
for(
int i = 
1; i <= n; i++) 
if(!outd[belong[i]])

    {

        printf(
"
%d 
", i);

    }

    printf(
"
\n
");

}

int main()

{

    
while(scanf(
"
%d
", &n) && n)

    {

        init();

        scanf(
"
%d
", &m);

        
while(m--)

        {

            
int u, v;

            scanf(
"
%d%d
", &u, &v);

            read_graph(u, v);

        }

        solve();

    }

    
return 
0;

}

转载于:https://www.cnblogs.com/g0feng/archive/2012/10/29/2745462.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95960988

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。