Pagini recente » Cod sursa (job #2416825) | Cod sursa (job #429982) | Cod sursa (job #2525437) | Cod sursa (job #587562) | Cod sursa (job #2927888)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
vector<int> graph[NMAX + 1], rev[NMAX + 1], stackOrder, comp[NMAX];
bool viz[NMAX + 1];
void dfs(int node, vector<int>* g, vector<int>& v) {
viz[node] = true;
for(auto neighbour : g[node]) {
if(viz[neighbour] == false) {
dfs(neighbour, g, v);
}
}
v.push_back(node);
}
int main() {
int n, m, nComp;
FILE *fin, *fout;
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
fscanf(fin, "%d%d", &n, &m);
for(int i = 0; i < m; i++) {
int a, b;
fscanf(fin, "%d%d", &a, &b);
graph[a].push_back(b);
rev[b].push_back(a);
}
for(int node = 1; node <= n; node++) {
if(viz[node] == false)
dfs(node, graph, stackOrder);
}
for(int node = 1; node <= n; node++)
viz[node] = false;
nComp = 0;
while(!stackOrder.empty()) {
int node = stackOrder.back();
stackOrder.pop_back();
if(viz[node] == false) {
dfs(node, rev, comp[nComp]);
nComp++;
}
}
fprintf(fout, "%d\n", nComp);
for(int i = 0; i < nComp; i++) {
for(auto node : comp[i])
fprintf(fout, "%d ", node);
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}