Pagini recente » Cod sursa (job #2652845) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2531500) | Cod sursa (job #347351) | Cod sursa (job #2165617)
#include <bits/stdc++.h>
#define INFILE "ctc.in"
#define OUTFILE "ctc.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
struct Graph{
vector<vector<int>> Adj;
void Init(int n){
Adj.resize(n+1);
}
void Add(int x,int y){
Adj[x].push_back(y);
}
};
Graph G;
Graph Gt;
int N,M;
void Read(){
in>>N>>M;
G.Init(N);
Gt.Init(N+1);
for(int i=1;i<=M;i++){
int x,y;
in>>x>>y;
G.Add(x,y);
Gt.Add(y,x);
}
}
void DFS(int x,vector<int>& noduri,bool viz[]){
viz[x]=true;
for(auto y:G.Adj[x]){
if(viz[y]) continue;
DFS(y,noduri,viz);
}
noduri.push_back(x);
}
void DFST(int x,bool viz[],vector<int>& componente){
viz[x]=true;
componente.push_back(x);
for(auto y:Gt.Adj[x]){
if(viz[y]) continue;
DFST(y,viz,componente);
}
}
void KosarjuSharir(){
bool viz[N+1];
vector<int> noduri;
vector<vector<int>> componente;
memset(viz,false,sizeof(viz));
for(int i=1;i<=N;i++){
if(!viz[i])
DFS(i,noduri,viz);
}
memset(viz,false,sizeof(viz));
while(!noduri.empty()){
int x=noduri.back();
noduri.pop_back();
if(viz[x]) continue;
vector<int> v;
DFST(x,viz,v);
componente.push_back(v);
}
out<<componente.size()<<"\n";
for(auto v:componente){
for(auto e:v){
out<<e<<" ";
}
out<<"\n";
}
}
int main(){
Read();
KosarjuSharir();
return 0;
}