Pagini recente » Cod sursa (job #2506657) | Cod sursa (job #2410249) | Cod sursa (job #1690563) | Cod sursa (job #643964) | Cod sursa (job #2169813)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
const int mmax = 200005, nmax = 100005;
int N, M, x, y, ssc, comp;
bool viz1[nmax];
int viz2[nmax];
vector < int > G[mmax],GT[mmax],sol[nmax];
stack < int > stiva;
void Citire () {
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;
sol[comp].push_back(nod);
for(unsigned i = 0; i < GT[nod].size(); i++) {
int v = GT[nod][i];
if (!viz2[v]) DFS2(v);
}
}
int main()
{
Citire();
DFS1(1);
for (int i = 2; 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 <= comp; i++) {
for(unsigned j = 0; j<sol[i].size(); j++)
fout << sol[i][j] << ' ';
fout << endl;
}
return 0;
}