Pagini recente » Cod sursa (job #1642835) | Cod sursa (job #376897) | Cod sursa (job #1234173) | Cod sursa (job #509185) | Cod sursa (job #2925798)
#include <bits/stdc++.h>
using namespace std;
#define NO_NODES 100000
int noNodes;
vector<int> graph[NO_NODES];
vector<int> revGraph[NO_NODES];
bool marked[NO_NODES];
vector<int> stackOrder;
vector<int> components[NO_NODES];
void addEdge(int x, int y) {
graph[x].push_back(y);
revGraph[y].push_back(x);
}
void resetMarked() {
memset(marked, false, sizeof(marked));
}
void dfs(vector<int>* graph, vector<int>& visited, int node) {
marked[node] = true;
for (int neighbour : graph[node])
if (!marked[neighbour])
dfs(graph, visited, neighbour);
visited.push_back(node);
}
int main() {
FILE *fin, *fout;
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
int noEdges, noComponents;
int x, y;
fscanf(fin, "%d%d", &noNodes, &noEdges);
while (noEdges--) {
fscanf(fin, "%d%d", &x, &y);
addEdge(x - 1, y - 1);
}
for (x = 0; x < noNodes; ++x)
if (!marked[x])
dfs(graph, stackOrder, x);
resetMarked();
noComponents = 0;
while (stackOrder.size()) {
x = stackOrder.back();
stackOrder.pop_back();
if (!marked[x]) {
dfs(revGraph, components[noComponents], x);
++noComponents;
}
}
fprintf(fout, "%d\n", noComponents);
for (x = 0; x < noComponents; ++x, fputc('\n', fout))
for (int node : components[x])
fprintf(fout, "%d ", node + 1);
fclose(fin);
fclose(fout);
return 0;
}