#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 5010
int v, e;
vector<int> mapa[MAXN], mapb[MAXN];
bool visite[MAXN], flag[MAXN];
int post[MAXN], ID[MAXN], in[MAXN],cnt= 0, c= 0;
void dfs( int t )
{
visite[t]= true;
for( size_t i= 0; i< mapb[t].size(); ++i )
if( !visite[ mapb[t][i] ] ) dfs( mapb[t][i] );
post[cnt++]= t;
}
void Ddfs( int t, int id )
{
visite[t]= true;
ID[t]= id;
for( size_t i= 0; i< mapa[t].size(); ++i )
if( !visite[ mapa[t][i] ] ) Ddfs( mapa[t][i], id );
}
void run()
{
memset( visite, false, sizeof(visite) );
for( int i= 1; i<= v; ++i )
if( !visite[i] ) dfs( i );
memset( visite, false, sizeof(visite) );
for( int i= cnt- 1; i>= 0; i-- )
if( !visite[ post[i] ] ) Ddfs( post[i], ++c );
memset( flag, false, sizeof( flag ) );
memset( in, false, sizeof(in) );
for( int i= 1; i<= v; ++i )
for( size_t j= 0; j< mapa[i].size(); ++j )
if( ID[i]!= ID[ mapa[i][j] ] ) in[ ID[i] ]++;
for( int i= 1; i<= v; ++i )
if( in[ ID[i] ]== 0 ) flag[i]= true;
bool ok= false;
for( int i= 1; i<= v; ++i )
if( flag[i] )
{
if( !ok )
{
printf("%d",i);
ok= true;
}
else printf(" %d",i );
}
printf("\n");
}
void initial()
{
for( int i= 0; i<= v; ++i )
mapa[i].clear(), mapb[i].clear();
cnt= 0, c= 0;
for( int i= 0; i< e; ++i )
{
int u, v;
scanf("%d%d",&u,&v );
mapa[u].push_back( v );
mapb[v].push_back( u );
}
}
int main()
{
while( scanf("%d%d",&v,&e)== 2 )
{
initial();
run();
}
return 0;
}
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define MAXN 5010
int v, e, cnt, c;
vector<int> map[MAXN];
deque<int> stack;
int low[MAXN], pre[MAXN], mark[MAXN], degree[MAXN];
void dfs( int w )
{
int min;
pre[w]= cnt++; low[w]= pre[w]; min= low[w];
stack.push_front(w);
for( size_t i= 0; i< map[w].size(); ++i )
{
if( pre[ map[w][i] ]== 0 ) dfs( map[w][i] );
if( low[ map[w][i] ]< min ) min= low[ map[w][i] ] ;
}
if( min< low[w] ) { low[w]= min; return; }
while( stack.front()!= w )
{
mark[ stack.front() ]= c;
low[ stack.front() ]= v;
stack.pop_front();
}
mark[w]= c++; stack.pop_front();
}
void solve()
{
memset( low, 0, sizeof(low) );
memset( pre, 0, sizeof(pre) );
memset( mark,0, sizeof(mark));
memset( degree, 0, sizeof(degree) );
cnt= 1, c= 1;
for( int i= 1; i<= v; ++i )
if( pre[i]== 0 ) dfs( i );
for( int i= 1; i<= v; ++i )
for( size_t j= 0; j< map[i].size(); ++j )
if( mark[i]!= mark[ map[i][j] ] ) degree[ mark[i] ]++;
bool ok= false;
for( int i= 1; i<= v; ++i )
if( degree[ mark[i] ]== 0 )
{
if( !ok )
{
printf("%d",i);
ok= true;
}
else printf(" %d",i );
}
printf("\n");
}
int main()
{
while( scanf("%d%d",&v,&e)== 2 )
{
int a, b;
for( int i= 0; i<= v; ++i )
map[i].clear();
for( int i= 0; i< e; ++i )
{
scanf("%d%d",&a,&b);
map[a].push_back(b);
}
solve();
}
return 0;
}
posted on 2008-12-05 21:46
Darren 阅读(247)
评论(0) 编辑 收藏 引用