Pagini recente » Cod sursa (job #1972063) | Cod sursa (job #382346) | Cod sursa (job #2024533) | Cod sursa (job #1451587) | Cod sursa (job #2440906)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
ifstream intrare("ctc.in");
ofstream iesire("ctc.out");
const int NMAX=100005;
int i,j,n,m,sol;
int vizitat[NMAX];
vector < int >graf[NMAX],graf2[NMAX],solutie[NMAX];
stack <int >s;
int DFS(int nodStart){
vizitat[nodStart]=1;
for(size_t i=0;i<graf[nodStart].size();i++){
int vecin=graf[nodStart][i];
if(!vizitat[vecin])
DFS(vecin);
}
s.push(nodStart);
}
int DFS2(int nodStart){
vizitat[nodStart]=2;
solutie[sol].push_back(nodStart);
for(size_t i=0;i<graf2[nodStart].size();i++){
int vecin=graf2[nodStart][i];
if(vizitat[vecin]==1){
// vizitat[vecin]=2;
DFS2(vecin);
}
}
}
int main()
{
intrare>>n>>m;
for(i=1;i<=m;i++)
{int o,l;
intrare>>o>>l;
graf[o].push_back(l);
graf2[l].push_back(o);
}
for(i=1;i<=n;i++)
if(!vizitat[i])
DFS(i);
while(!s.empty()){
int nod=s.top();
if(vizitat[nod]==1){
sol++;
DFS2(nod);
}
s.pop();
}
iesire<<sol;
for(j=1;j<=sol;j++){
iesire<<endl;
for(size_t i=0;i<solutie[j].size();i++)
iesire <<solutie[j][i]<<" ";
}
return 0;
}