Pagini recente » Cod sursa (job #1488929) | Cod sursa (job #1183719) | Cod sursa (job #1967058) | Cod sursa (job #176354) | Cod sursa (job #2671392)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define MAX_N 100002
int N, M;
vector<int> links[MAX_N];
vector<int> tlinks[MAX_N]; // transposed
stack<int> order;
bool visited[MAX_N];
vector<int> components[MAX_N];
int nr;
void dfs( int node ){
visited[node] = true;
for ( auto &x : links[node] ){
if ( !visited[x] )
dfs(x);
}
order.push(node);
}
void tdfs( int node ){
components[nr].push_back(node);
visited[node] = false;
for ( auto &x : tlinks[node] ){
if ( visited[x] )
tdfs(x);
}
}
int main(){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
int a, b;
for ( int i = 0; i < M; i++ ){
fin >> a >> b;
links[a].push_back(b);
tlinks[b].push_back(a);
}
for ( int i = 1; i <= N; i++ ){
if ( !visited[i] )
dfs(i);
}
while(!order.empty()){
int x = order.top();
if ( visited[x] ){
nr++;
tdfs(x);
}
order.pop();
}
fout << nr << '\n';
for ( int i = 1; i<= nr; i++ ){
for ( auto &x : components[i] ){
fout << x << ' ';
}
fout << "\n";
}
}