Pagini recente » Cod sursa (job #3031504) | Cod sursa (job #1190916) | Cod sursa (job #3263396) | Cod sursa (job #416454) | Cod sursa (job #2928349)
// Mihai Priboi
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
int n, m;
vector<int> graph[MAXN + 1], revGraph[MAXN + 1];
vector<int> order;
vector<int> comp[MAXN + 1];
bool marked[MAXN + 1];
void dfs(int node, vector<int>* graph, vector<int>& v) {
marked[node] = true;
for(int neighbour : graph[node])
if(!marked[neighbour])
dfs(neighbour, graph, v);
v.push_back(node);
}
int main() {
FILE *fin, *fout;
int i, x, y, node, compNo;
fin = fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(i = 0; i < m; i++) {
fscanf(fin, "%d%d", &x, &y);
graph[x].push_back(y);
revGraph[y].push_back(x);
}
fclose(fin);
for(i = 1; i <= n; i++)
if(!marked[i])
dfs(i, graph, order);
memset(marked, 0, n + 1);
compNo = 0;
while(!order.empty()) {
node = order.back();
order.pop_back();
if(!marked[node])
dfs(node, revGraph, comp[compNo++]);
}
fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", compNo);
for(i = 0; i < compNo; i++) {
for(int node : comp[i])
fprintf(fout, "%d ", node);
fprintf(fout, "\n");
}
fclose(fout);
return 0;
}