Pagini recente » Cod sursa (job #1772278) | Cod sursa (job #2070507) | Cod sursa (job #3168213) | Cod sursa (job #1419978) | Cod sursa (job #1969516)
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#define NMax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMax], Gt[NMax], ctc[NMax];
int N, M, i, j, a, b, nrsol, st[NMax], viz[NMax];
void DFS (int x)
{
viz[x]=1;
for(int i=0; i<G[x].size(); i++)
if(!viz[G[x][i]])
DFS(G[x][i]);
st[++st[0]]=x;
}
void DFST (int x)
{
viz[x]=1;
for(int i=0; i<Gt[x].size(); i++)
if(!viz[Gt[x][i]])
DFST(Gt[x][i]);
ctc[nrsol].pb(x);
}
int main()
{
f>>N>>M;
for(i=1; i<=M; i++)
{
f>>a>>b;
G[a].pb(b);
Gt[b].pb(a);
}
for(i=1; i<=N; i++)
if(!viz[i])
DFS(i);
memset(viz, 0, sizeof(viz));
for(i=N; i>=1; i--)
if(!viz[st[i]])
{
++nrsol;
DFST(st[i]);
}
g<<nrsol<<'\n';
for(i=1; i<=nrsol; i++)
{
for(j=0; j<ctc[i].size(); j++)
g<<ctc[i][j]<<' ';
g<<'\n';
}
return 0;
}