Pagini recente » Monitorul de evaluare | Cod sursa (job #1898792) | Cod sursa (job #2329152) | Cod sursa (job #857633) | Cod sursa (job #3303674)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 1e5;
int n, m, x, y, num_comp;
bool vis[NMAX + 2];
int comp[NMAX + 2];
vector<int> G[NMAX + 2], Gt[NMAX + 2];
vector<int> S;
void dfs(int node, vector<int> G[], int curr_comp) {
comp[node] = curr_comp;
for (auto nxt : G[node]) {
if (!comp[nxt]) {
dfs(nxt, G, curr_comp);
}
}
}
void sort_top (int node) {
vis[node] = true;
for (auto nxt : G[node]) {
if (!vis[nxt]) {
sort_top(nxt);
}
}
S.push_back(node);
}
int main() {
fin >> n >> m;
while (m--) {
fin >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
sort_top(i);
}
}
reverse(S.begin(), S.end());
memset(vis, 0, sizeof(vis));
for (auto x : S) {
if (!comp[x]) {
dfs(x, Gt, ++num_comp);
}
}
vector<vector<int>> comps(num_comp);
for (int i = 1; i <= n; i++) {
comps[comp[i] - 1].push_back(i);
}
fout << num_comp << '\n';
for (auto component : comps) {
for (auto node : component) {
fout << node << ' ';
}
fout << '\n';
}
return 0;
}