Pagini recente » Cod sursa (job #2562347) | Cod sursa (job #3001763) | Cod sursa (job #525748) | Cod sursa (job #33915) | Cod sursa (job #580798)
Cod sursa(job #580798)
#include<stdio.h>
#include<vector>
#include<stack>
#define dmax 100003
using namespace std;
int n,m,nrc;
bool t[dmax];
vector<int>g[dmax],gt[dmax],comp[dmax];
vector<int>::iterator it;
stack<int>st;
void dfs1(int k)
{
vector<int>::iterator ir;
for(ir = g[k].begin(); ir < g[k].end(); ir++)
if(!t[*ir])
{
t[*ir] = 1;
dfs1(*ir);
st.push(*ir);
}
}
void dfs2(int k)
{
vector<int>::iterator ir;
for(ir = gt[k].begin(); ir < gt[k].end(); ir++)
if(t[*ir])
{
t[*ir] = 0;
comp[nrc].push_back(*ir);
dfs2(*ir);
}
}
void ctc()
{
int i,x;
for(i=1; i<=n; i++)
if(!t[i])
{
t[i] = 1;
dfs1(i);
st.push(i);
}
while(!st.empty() )
{
while(!st.empty() && !t[st.top()])
st.pop();
if(!st.empty() )
{
nrc++;
x = st.top();
comp[nrc].push_back(x);
t[x] = 0;
dfs2(x);
}
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i,a,b;
scanf("%d %d", &n, &m);
for(i=1;i<=m;i++)
{
scanf("%d %d", &a, &b);
g[a].push_back(b);
gt[b].push_back(a);
}
ctc();
printf("%d\n", nrc);
for(i=1; i<=nrc; i++)
{ for(it = comp[i].begin(); it < comp[i].end(); it++)
printf("%d ", *it);
printf("\n");
}
return 0;
}