Pagini recente » Cod sursa (job #19072) | Cod sursa (job #2665085) | Cod sursa (job #2645748) | Cod sursa (job #2070680) | Cod sursa (job #2842682)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <vector <int>> G, GT;
vector <bool> p, f;
vector <int> ctc;
int n, m;
void DFS(int node) {
p[node] = true;
for(auto x : G[node])
if(!p[x]) DFS(x);
}
void DFST(int node) {
f[node] = true;
for(auto y : GT[node])
if(!f[y]) DFST(y);
}
int main() {
fin >> n >> m;
G = GT = vector <vector <int>> (n + 1);
ctc = vector <int> (n + 1, 0);
for(int i = 1; i <= m; i ++) {
int x, y; fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
vector <vector <int>> ans;
for(int i = 1; i <= n; i ++)
if(ctc[i] == 0) {
vector <int> TC;
p = f = vector <bool> (n + 1, false);
DFS(i); DFST(i);
for(int j = 1; j <= n; j ++)
if(p[j] && f[j]) {
TC.push_back(j);
ctc[j] = ans.size() + 1;
}
ans.push_back(TC);
}
fout << ans.size() << '\n';
for(auto x : ans) {
for(auto y : x) fout << y << ' ';
fout << '\n';
}
return 0;
}