Pagini recente » Cod sursa (job #2575869) | Cod sursa (job #486131) | Cod sursa (job #982263) | Cod sursa (job #2931878) | Cod sursa (job #939980)
Cod sursa(job #939980)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
vector<int> ctc,v[100005],vt[100005],sol[100005];
stack<int> st;
vector<bool> viz;int cnt;
void dfs_plus(int u)
{
if(!viz[u])
{
viz[u]=true;
for_each(v[u].begin(),v[u].end(),dfs_plus);
st.push(u);
}
}
void dfs_minus(int u)
{
if(ctc[u]==-1)
{
ctc[u]=cnt;
for_each(vt[u].begin(),vt[u].end(),dfs_minus);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
x--;y--;
v[x].push_back(y);
vt[y].push_back(x);
}
viz.assign(n,false);
for(int i=0;i<n;i++)
dfs_plus(i);
ctc.assign(n,-1);
while(!st.empty())
{
if(ctc[st.top()]==-1)
dfs_minus(st.top()),
cnt++;
st.pop();
}
for(int i=0;i<n;i++)
sol[ctc[i]].push_back(i);
printf("%d\n",cnt);
for(int i=0;i<cnt;i++,printf("\n"))
for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();++it,printf(" "))
printf("%d",*it+1);
return 0;
}