Pagini recente » Cod sursa (job #2635475) | Cod sursa (job #3276702) | Cod sursa (job #1402107) | Cod sursa (job #3005037) | Cod sursa (job #3251816)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<vector<int>>gr,gr_t;
vector<int>folosit,rasp;
stack<int>s;
int nr_com_conx=0;
void DFS(int nod){
for(int i=0;i<gr[nod].size();i++){
if(folosit[gr[nod][i]]==-1){
folosit[gr[nod][i]]=1;
DFS(gr[nod][i]);
}
}//vizitez mai intai toti vecini sai,de-abia dupa
//pot sa spun ca am finalizat nodul respectiv
s.push(nod);
}
void DFS1(int nod){
rasp.push_back(nod);
for(int i=0;i<gr_t[nod].size();i++){
if(folosit[gr_t[nod][i]]==-1){
folosit[gr_t[nod][i]]=1;
DFS1(gr_t[nod][i]);
}
}
}
int n,m,nod1,nod2;
int main(){
cin>>n>>m;
gr.resize(n+1);
gr_t.resize(n+1);
folosit.resize(n+1,-1);
for(int i=1;i<=m;i++){
cin>>nod1>>nod2;
gr[nod1].push_back(nod2);
gr_t[nod2].push_back(nod1);
}
for(int i=1;i<=n;i++){
if(folosit[i]==-1){
folosit[i]=1;
DFS(i);
}
}
for(int i=1;i<=n;i++){
folosit[i]=-1;
}
int nod_curent;
while(!s.empty()){
nod_curent=s.top();
s.pop();
if(folosit[nod_curent]==-1){
nr_com_conx+=1;
folosit[nod_curent]=1;
DFS1(nod_curent);
rasp.push_back(-1);
}
}
cout<<nr_com_conx<<'\n';
for(int i=0;i<rasp.size();i++){
if(rasp[i]==-1){
cout<<'\n';
}else{
cout<<rasp[i]<<" ";
}
}
gr.clear();
gr_t.clear();
folosit.clear();
rasp.clear();
}