Pagini recente » Cod sursa (job #1891064) | Cod sursa (job #1100638) | Cod sursa (job #2944318) | Cod sursa (job #720290) | Cod sursa (job #2849588)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 1e5;
const int MMAX = 2e5;
int viz[NMAX + 2];
int ctc[NMAX + 2];
vector <int> ans[NMAX + 2];
int currComp;
vector <int> g[NMAX + 2], ginv[NMAX + 2];
vector <int> order;
void dfs_topological (int node) {
viz[node] = 1;
for (int next : g[node])
if (!viz[next]) {
dfs_topological(next);
order.push_back(next);
}
}
void dfs_ctc (int node) {
viz[node] = 1;
ctc[node] = currComp;
ans[currComp].push_back(node);
for (int next : ginv[node])
if (!viz[next]) {
dfs_ctc(next);
}
}
int main() {
int n, m, i, x, y;
fin >> n >> m;
for (i = 1; i <= m; ++i) {
fin >> x >> y;
g[x].push_back(y);
ginv[y].push_back(x);
}
for (i = 1; i <= n; ++i)
if (!viz[i])
dfs_topological(i);
for (i = 1; i <= n; ++i) viz[i] = 0;
currComp = 1;
for (i = order.size() - 1; i >= 0; --i)
if (!viz[order[i]]) {
dfs_ctc(order[i]);
++currComp;
}
fout << currComp - 1 << "\n";
for (i = 1; i <= currComp; ++i, fout << "\n")
for (int x : ans[i])
fout << x << " ";
return 0;
}