Pagini recente » Cod sursa (job #3237864) | Cod sursa (job #247881) | Cod sursa (job #2137375) | Cod sursa (job #1120536) | Cod sursa (job #2218278)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector < int > g[MAXN + 1], gt[MAXN + 1], ord;
vector < vector < int > > ctc;
int seen[MAXN + 1];
void norm_dfs(int node) {
seen[node] = 1;
for (auto it : g[node])
if (seen[it] == 0)
norm_dfs(it);
ord.push_back(node);
}
void rev_dfs(int node, vector < int >& comp) {
seen[node] = 0;
comp.push_back(node);
for (auto it : gt[node])
if (seen[it])
rev_dfs(it, comp);
}
int main()
{
int n, m;
ifstream fin("ctc.in");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
fin.close();
for (int i = 1; i <= n; ++i)
if (seen[i] == 0)
norm_dfs(i);
while (ord.empty() == false) {
if (seen[ord.back()]) {
vector < int > comp;
rev_dfs(ord.back(), comp);
ctc.push_back(comp);
}
ord.pop_back();
}
ofstream fout("ctc.out");
fout << ctc.size() << '\n';
for (auto comp : ctc) {
for (auto it : comp)
fout << it << " ";
fout << '\n';
}
fout.close();
return 0;
}