Pagini recente » Cod sursa (job #1051714) | Profil VladCiofu | Statistici Yvofloarea1 (YvoFloarea) | Istoria paginii utilizator/colincj | Cod sursa (job #1332487)
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <list>
#include <iterator>
using namespace std;
#define DMAX 10//100002
int N, M, timeR, G_Tr = 1, v_put = 1, nrCTC;
struct Nod{
int u, d, f;
vector<int> Adj, AdjT;
} G[DMAX];
vector<int> V, CV;
void citire(){
int i, x, y;
scanf("%d %d", &N, &M);
for ( i = 0; i < M; i++){
scanf("%d %d\n", &x, &y);
G[x].Adj.push_back(y);
G[y].AdjT.push_back(x);
}
}
void DFS(int root){
int i, lg, chld;
if (G_Tr) lg = G[root].Adj.size();
else lg = G[root].AdjT.size();
G[root].u++;
G[root].d = ++timeR;
for (i = 0; i < lg; i++){
if(G_Tr) chld = G[root].Adj[i];
else chld = G[root].AdjT[i];
if (G[chld].u < G[root].u){
DFS(chld);
}
}
G[root].f = ++timeR;
if(v_put) V.push_back(root);
}
int main(){
int i;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
for (i = 1; i <= N; i++) {
if (!G[i].u) {
DFS(i);
}
}
G_Tr = 0; v_put = 0;
for (i = V.size() - 1; i >= 0; i--) {
if (G[V[i]].u == 1){
DFS(V[i]);
nrCTC++;
}
}
cout << nrCTC << '\n';
v_put = 1; CV = V;
for (i = CV.size() - 1; i >= 0; i--)
if (G[CV[i]].u == 2){
V.clear();
DFS(CV[i]);
for (int j = 0; j < V.size(); j++)
cout << V[j] << ' ';
cout << '\n';
}
return 0;
}