Pagini recente » Cod sursa (job #2065337) | Cod sursa (job #2687588) | Cod sursa (job #2796683) | Cod sursa (job #2443643) | Cod sursa (job #2314929)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
vector <int> G[N],Gt[N];
vector <int> CTC[N]; ///elem componentelor
stack <int> S;
int ct; //nr comp
int vf;
bool viz[N],vizt[N]; ///dfs pe ambele
void Read()
{ int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x); //graf transpus
}
fin.close();
}
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]);
S.push(x);
}
void DFSt(int x)
{
vizt[x]=1;
CTC[ct].push_back(x);
for(int i=0;i<Gt[x].size();i++)
if(!vizt[Gt[x][i]])
DFSt(Gt[x][i]);
}
void Do()
{
while(!S.empty())
{ vf=S.top(); S.pop();
if(!vizt[vf]) { ct++; DFSt(vf); }
}
}
void Timpi()
{
for(int i=1;i<=n;i++)
if(!viz[i]) DFS(i);
}
void Write()
{ fout<<ct<<"\n";
for(int i=1;i<=n;i++)
{for(int j=0;j<CTC[i].size();j++)
fout<<CTC[i][j]<<" ";
fout<<"\n";
}
fout.close();
}
int main()
{
Read();
Timpi();
Do();
Write();
return 0;
}