Pagini recente » Cod sursa (job #1771724) | Cod sursa (job #1544969) | Cod sursa (job #821898) | Cod sursa (job #3263040) | Cod sursa (job #2084768)
#include <bits/stdc++.h>
#define NN 100001
using namespace std;
stack<int>st;
vector<int>v;
int n , m ,componente;
bool used[NN],viz[NN];
struct nod
{
int info ;
nod *next;
}*G[100001], *GT[100001];
void add_G( int x, int y )
{
nod * aux = new nod ;
aux -> info = y ;
aux -> next = G[x];
G[x] = aux ;
}
void add_GT( int x, int y )
{
nod * aux = new nod ;
aux -> info = y ;
aux -> next = GT[x];
GT[x] = aux ;
}
void scan()
{
freopen("ctc.in","r",stdin);
scanf ("%d%d" , &n , &m) ;
for ( int i = 1; i<= m ; ++ i )
{
int x ,y ;
scanf("%d%d",&x,&y);
add_G(x,y);
add_GT(y,x);
}
}
void first_dfs( int node )
{
used [node] = true ;
for ( nod * aux =G[node]; aux ; aux = aux ->next)
if(!used[aux->info])first_dfs(aux->info);
st.push(node);
}
void dfs(int node )
{ v.push_back(node);
viz[node]=true ;
for ( nod * aux = GT[node]; aux ; aux = aux ->next)
if(!viz[aux->info])dfs(aux->info);
}
int main()
{
scan();
for ( int i = 1 ; i <= n ; ++ i )
if(!used[i]) first_dfs(i);
// in stack am valorile in ordinea timpilor de finish
while(!st.empty())
{
if(viz[st.top()])st.pop();
else { componente ++ ;
dfs(st.top());
v.push_back(0);
}
}
freopen("ctc.out","w",stdout);
for ( int i = 0 ; i < v.size() ; ++ i )
{
if(v[i]==0)printf("\n");
else printf("%d ",v[i]);
}
return 0;
}