POJ 2553 The Bottom of a Graph
7096 ワード
図の底を求めて、縮み点を通った図の中で出度が0の点を探し出して、各点の中の要素は図の底です.そして
スペースを多く出力しないで、秩序正しく出力します.tarjanアルゴリズムをよく叩いた.
スペースを多く出力しないで、秩序正しく出力します.tarjanアルゴリズムをよく叩いた.
/*Accepted 468K 47MS C++ 1864B 2012-07-30 14:44:59*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int MAXN = 5050;
const int MAXM = MAXN * MAXN;
int first[MAXN], next[MAXM], v[MAXM], cnt, top, col, e, N, M, k;
int dfn[MAXN], s[MAXN], low[MAXN], outdgr[MAXN], color[MAXN], ins[MAXN];
void tarjan(int cur)
{
int i;
dfn[cur] = low[cur] = ++ cnt;
s[top ++] = cur, ins[cur] = 1;
for(i = first[cur]; i != -1; i = next[i])
{
if(!dfn[v[i]])
{
tarjan(v[i]);
if(low[v[i]] < low[cur])
low[cur] = low[v[i]];
}
else if(dfn[v[i]] < low[cur] && ins[v[i]])
low[cur] = dfn[v[i]];
}
if(low[cur] == dfn[cur])
{
++ col;
for(s[top] = -1; s[top] != cur; )
color[s[-- top]] = col, ins[s[top]] = 0;
}
}
void cal()
{
int i, j;
cnt = top = col = 0;
memset(dfn, 0, sizeof dfn);
memset(ins, 0, sizeof ins);
for(i = 1; i <= N; i ++)
if(!dfn[i])
tarjan(i);
memset(outdgr, 0, sizeof outdgr);
for(i = 1; i <= N; i ++)
for(j = first[i]; j != -1; j = next[j])
if(color[i] != color[v[j]])
++ outdgr[color[i]];
k = 0;
for(i = 1; i <= N; i ++)
{
if(outdgr[color[i]] == 0)
{
if(k ++) printf(" ");
printf("%d", i);
}
}
printf("
");
}
void addedge(int x, int y)
{
v[e] = y;
next[e] = first[x], first[x] = e ++;
}
void ReadGraph()
{
int x, y;
e = 0;
memset(first, -1, sizeof first);
while(M --)
{
scanf("%d%d", &x, &y);
addedge(x, y);
}
}
int main()
{
while(scanf("%d", &N) != EOF)
{
if(N == 0) break;
scanf("%d", &M);
ReadGraph();
cal();
}
return 0;
}