Pagini recente » Monitorul de evaluare | Cod sursa (job #955653) | Cod sursa (job #1492180) | Cod sursa (job #138402) | Cod sursa (job #1920335)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G1[100010];
vector <int> G2[100010];
vector <int> C[100010];
struct str
{
int nod,dist;
}F[100010];
bool myfunction (str i,str j) { return (i.dist>j.dist); }
int viz[100010],viz1[100010],n,m,tp,nrnod;
void DFS1(int x,int comp)
{
nrnod++;
F[x].dist=++tp;
F[x].nod=x;
viz[x]=comp;
for(int i=0;i<G1[x].size();i++)
if(!viz[G1[x][i]]) DFS1(G1[x][i],comp);
F[x].dist=++tp;
}
void DFS2(int x, int comp)
{
nrnod++;
C[comp].push_back(x);
viz1[x]=comp;
for(int i=0;i<G2[x].size();i++)
if(!viz1[G2[x][i]]) DFS2(G2[x][i],comp);
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
f>>a>>b;
G1[a].push_back(b);
G2[b].push_back(a);
}
int comp=0;
for(int i=1;i<=n && nrnod<n;i++)
if(!viz[i]) DFS1(i,++comp);
sort(F+1,F+n+1,myfunction);
nrnod=0;
comp=0;
for(int i=1;i<=n && nrnod<n;i++)
if(!viz1[F[i].nod]) DFS2(F[i].nod,++comp);
g<<comp<<'\n';
for(int i=1;i<=comp;i++)
{
for(int j=0;j<C[i].size();j++)
g<<C[i][j]<<' ';
g<<'\n';
}
return 0;
}