Pagini recente » Cod sursa (job #1254812) | Cod sursa (job #1860022) | Cod sursa (job #2822830) | Cod sursa (job #266486) | Cod sursa (job #2187277)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector <int> G[2][100005];
vector <int> comp[100005];
stack <int> kosaraju;
int viz[100005],m,n,cnt;
void dfs(int nod,int t)
{
viz[nod]=1;
for(auto fiu:G[t][nod])
{
if(!viz[fiu])
{
dfs(fiu,t);
}
}
if(t==0)
kosaraju.push(nod);
else
comp[cnt].push_back(nod);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
int nod1,nod2;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&nod1,&nod2);
G[0][nod1].push_back(nod2);
G[1][nod2].push_back(nod1);
}
for(int i=1; i<=n; i++)
if(!viz[i])
dfs(i,0);
memset(viz,0,sizeof(viz));
while(!kosaraju.empty())
{
if(!viz[kosaraju.top()])
{
cnt++;
dfs(kosaraju.top(),1);
}
kosaraju.pop();
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
for(auto nod:comp[i])
printf("%d ",nod);
printf("\n");
}
return 0;
}