Pagini recente » Cod sursa (job #2698634) | Cod sursa (job #697000) | Cod sursa (job #2780312) | Cod sursa (job #3262416) | Cod sursa (job #3284102)
#include <fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<vector<int>> graph;
vector<vector<int>> rgraph;
void dfs1(int u,vector<bool>& visited,vector<int>& path){
visited[u]=true;
for(auto v:graph[u]){
if(!visited[v]){
dfs1(v,visited,path);
}
}
path.push_back(u);
}
void dfs2(int u,vector<bool>& visited,vector<int>& path){
visited[u]=true;
for(auto v:rgraph[u]){
if(!visited[v]){
dfs2(v,visited,path);
}
}
path.push_back(u);
}
vector<vector<int>> getCTC(int n){
vector<bool> visited=vector<bool>(n+2,false);
vector<int> path;
for(int i=1;i<=n;i++){
if(!visited[i])
dfs1(i,visited,path);
}
reverse(path.begin(),path.end());
visited=vector<bool>(n+2,false);
vector<vector<int>> ctc;
for(auto v:path){
if(!visited[v]){
ctc.push_back({});
dfs2(v,visited,*ctc.rbegin());
}
}
return ctc;
}
int main()
{
int i,j,n,m,u,v;
cin>>n>>m;
graph.resize(n+2);
rgraph.resize(n+2);
for(i=0;i<m;i++){
cin>>u>>v;
graph[u].push_back(v);
rgraph[v].push_back(u);
}
vector<vector<int>> ctc = getCTC(n);
cout<<ctc.size()<<"\n";
for(auto v:ctc){
for(auto u:v){
cout<<u<<" ";
}
cout<<"\n";
}
return 0;
}