Pagini recente » Cod sursa (job #16910) | Cod sursa (job #140610) | Cod sursa (job #2769510) | Cod sursa (job #1095323) | Cod sursa (job #2928230)
#include <fstream>
#include <string.h>
#include <vector>
#define MAXN 100000
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
vector<int> graph[MAXN];
vector<int> revGraph[MAXN];
bool marked[MAXN];
vector<int> stackOrder;
vector<int> components[MAXN];
int noComponents;
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) {
int neighbour;
marked[node] = true;
for (int i = 0; i < graph[node].size(); i++ ){
neighbour = graph[node][i];
if (!marked[neighbour])
dfs(graph, visited, neighbour);
}
visited.push_back(node);
}
int main() {
int n, m, i, x, y, j;
fin >> n >> m;
for( i = 1; i <= m; i++ ){
fin >> x >> y;
addEdge( x - 1, y - 1 );
}
for (x = 0; x < n; 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;
}
}
fout << noComponents << '\n';
for( i = 0; i < noComponents; i++ ){
for( j = 0; j < components[i].size(); j++ )
fout << components[i][j] + 1 << ' ';
fout << '\n';
}
return 0;
}