Pagini recente » Cod sursa (job #2440983) | Cod sursa (job #633232) | Cod sursa (job #1079009) | Cod sursa (job #665660) | Cod sursa (job #1328876)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#define Nmax 100100
#define neighbour(G) G[node][i]
using namespace std;
vector <int> Graph[Nmax], GraphT[Nmax], Component[Nmax];
int N, Components, Index, Order[Nmax];
bool seen[Nmax];
void Dfs(int node) {
seen[node] = true;
Component[Components].push_back(node);
for(int i = 0; i < GraphT[node].size(); i++)
if(!seen[neighbour(GraphT)])
Dfs(neighbour(GraphT));
}
void sortTop(int node) {
seen[node] = true;
for(int i = 0; i < Graph[node].size(); i++)
if(!seen[neighbour(Graph)])
sortTop(neighbour(Graph));
Order[++Index] = node;
}
void Solve() {
int i;
for(i = 1; i <= N; i++)
if(!seen[i])
Dfs(i);
reverse(Order + 1, Order + N + 1);
memset(seen, 0, sizeof(seen));
for(i = 1; i <= N; i++)
if(!seen[Order[i]]) {
Components++;
Dfs(Order[i]);
}
}
void Read() {
int x, y, M;
ifstream in("ctc.in");
in >> N >> M;
while(M--) {
in >> x >> y;
Graph[x].push_back(y);
GraphT[y].push_back(x);
}
in.close();
}
void Write() {
int i, j;
ofstream out("ctc.out");
out << Components << '\n';
for(i = 1; i <= Components; i++) {
for(j = 0; j < Component[i].size(); j++)
out << Component[i][j] << ' ';
out << '\n';
}
out << '\n';
out.close();
}
int main() {
Read();
Solve();
Write();
return 0;
}