Pagini recente » Cod sursa (job #1487279) | Cod sursa (job #2491324) | Cod sursa (job #1365136) | Cod sursa (job #2730926) | Cod sursa (job #2169928)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int mmax = 200005, nmax = 100005;
int N,M,ssc,comp,viz2[nmax];
bool viz1[nmax];
vector <int> G[mmax],GT[mmax],sol[mmax];
stack <int> stiva;
void Citire () {
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
}
}
void DFS1(int nod) {
viz1[nod]=true;
for(unsigned i=0; i<G[nod].size(); ++i) {
int v=G[nod][i];
if (!viz1[v]) DFS1(v);
}
stiva.push(nod);
}
void DFS2(int nod) {
viz2[nod]=comp;
for(unsigned i=0; i<GT[nod].size(); ++i) {
int v=GT[nod][i];
if (!viz2[v]) DFS2(v);
}
}
int main()
{
Citire();
for (int i=1; i<=N; ++i)
if(!viz1[i]) DFS1(i);
while(!stiva.empty()) {
ssc=stiva.top();
stiva.pop();
if(viz2[ssc]==0){
comp++;
DFS2(ssc);
}
}
fout<<comp<<"\n";
for(int i=1; i<=N; ++i)
sol[viz2[i]].push_back(i);
for(int i=1; i<=comp; ++i) {
for(unsigned j=0; j<sol[i].size(); ++j)
fout<<sol[i][j]<<' ';
fout<<"\n";
}
return 0;
}