Pagini recente » Cod sursa (job #1051922) | Cod sursa (job #1216812) | Cod sursa (job #1484298) | Cod sursa (job #1950112) | Cod sursa (job #3328377)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std ;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int seen[10000001] , viz[1000001] ;
stack<int> rez ;
void dfs1(int start , vector<vector<int> >&G ){
seen[start] = 1 ;
for(int j = 0 ; j < G[start].size() ; j ++) {
int nei = G[start][j];
if(!seen[nei])
{
dfs1(nei,G);
}
}
rez.push(start);
}
void dfs2(int start , vector<vector<int> >> , vector<int>&path){
if(!viz[start])
path.push_back(start);
viz[start] = 1 ;
for(int j = 0 ; j < GT[start].size() ; j ++ ){
int nei = GT[start][j];
if(!viz[nei]){
dfs2(nei,GT,path);
}
}
}
int main(){
int n , m ;
cin>>n>>m;
vector<vector<int> > G(n+1) , GT(n+1);
int x , y ;
for(int i = 1 ; i <= m ; i ++ )
{
cin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i =1 ; i <= n ; i ++ )
if(!seen[i])
dfs1(i,G);
vector<vector<int> > conex ;
while(!rez.empty()){
int nod = rez.top();
vector<int> path ;
if(!viz[nod]){
dfs2(nod,GT,path);
conex.push_back(path);
}
rez.pop();
}
sort(conex.begin(),conex.end());
cout<<conex.size()<<'\n';
for(int i = 0 ; i < conex.size() ; i ++ )
{
sort(conex[i].begin(),conex[i].end());
for(int j = 0 ; j < conex[i].size() ; j ++ )
cout<<conex[i][j]<< ' ';
cout<<'\n';
}
return 0 ;
}