Pagini recente » Cod sursa (job #1073241) | Istoria paginii runda/777momento | Cod sursa (job #1045766) | Cod sursa (job #2489730) | Cod sursa (job #2969555)
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int mx = 100001;
int n,m;
vector<int> g[mx],gt[mx];
vector<int> sorted;
vector<bool> visited;
void read(){
in>>n>>m;
int a,b;
visited.resize(n+1,false);
for(int i=0;i<m;i++){
in>>a>>b;
g[a].push_back(b);
gt[b].push_back(a);
}
}
void dfs1(int node){
visited[node] = true;
for(int k:gt[node]){
if(!visited[k])
dfs1(k);
}
sorted.push_back(node);
}
void dfs2(int node){
visited[node] = true;
for(int k:g[node]){
if(!visited[k]){
dfs2(k);
}
}
}
void dfs3(int node,vector<int>&comp){
comp.push_back(node);
visited[node] = true;
for(int k:g[node]){
if(!visited[k]){
dfs3(k,comp);
}
}
}
void solve(){
for(int i=1;i<=n;i++){
if(!visited[i])
dfs1(i);
}
visited.assign(n+1,false);
int cnt = 0;
for(auto x = sorted.rbegin();x!=sorted.rend();x++){
int p = *x;
if(!visited[p]){
dfs2(p);
cnt++;
}
}
out<<cnt<<'\n';
visited.assign(n+1,false);
for(auto x = sorted.rbegin();x!=sorted.rend();x++){
int p = *x;
if(!visited[p]){
vector<int> comp;
dfs3(p,comp);
for(int x:comp)
out<<x<<" ";
out<<'\n';
}
}
}
int main(){
read();
solve();
return 0;
}