Pagini recente » Cod sursa (job #1543980) | Cod sursa (job #813935) | Cod sursa (job #3165988) | Cod sursa (job #990352) | Cod sursa (job #1985485)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, x, y, components, viz[NMAX];
vector < int > G[NMAX], GT[NMAX], tsort;
vector < int > CTC[NMAX];
void dfs(int node) {
viz[node] = 1;
for (auto it : G[node]) {
if (!viz[it]) {
dfs(it);
}
}
tsort.push_back(node);
}
void dfs2(int node) {
viz[node] = 0;
CTC[components].push_back(node);
for (auto it : GT[node]) {
if (viz[it]) {
dfs2(it);
}
}
}
int main() {
f >> N >> M;
for (int i = 1; i <= M; ++i) {
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for (int i = 1; i <= N; ++i) {
if (!viz[i]) {
dfs(i);
}
}
for (int i = N - 1; i >= 0; --i) {
if (viz[tsort[i]]) {
dfs2(tsort[i]);
++components;
}
}
g << components << '\n';
for (int i = 0; i < components; ++i) {
sort(CTC[i].begin(), CTC[i].end());
for (auto it : CTC[i]) {
g << it << ' ';
}
g << '\n';
}
return 0;
}