Pagini recente » Cod sursa (job #2527950) | Cod sursa (job #1917613) | Cod sursa (job #2638935) | Cod sursa (job #1188530) | Cod sursa (job #2767812)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define maxi 100000
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,cnt;
vector<int> G[1+maxi],GT[1+maxi],SOL[1+maxi],F;
vector<int>::iterator I;
bool viz1[1+maxi],viz2[1+maxi];
void READ()
{
int a,b;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>a>>b;
G[a].push_back(b);
GT[b].push_back(a);
}
f.close();
return;
}
void DFS(int x)
{
viz1[x]=true;
for(auto a:G[x])
if(!viz1[a])
DFS(a);
F.push_back(x);
}
void DFSGT(int x,int cnt)
{
viz2[x]=true;
SOL[cnt].push_back(x);
for(auto a:GT[x])
if(!viz2[a])
DFSGT(a,cnt);
}
void KOSARAJU()
{
for(int i=1;i<=n;i++)
if(!viz1[i])
DFS(i);
for(I=F.end()-1;I>=F.begin();I--)
{
if(!viz2[*I])
cnt++,DFSGT(*I,cnt);
}
g<<cnt<<endl;
for(int i=1;i<=cnt;i++)
sort(SOL[i].begin(),SOL[i].end());
for(int i=1;i<=cnt;i++)
{
for(auto a:SOL[i])
g<<a<<" ";
g<<'\n';
}
g.close();
return;
}
int main()
{
READ();
KOSARAJU();
return 0;
}