Pagini recente » Cod sursa (job #1236817) | Cod sursa (job #1694088) | Cod sursa (job #1720750) | Cod sursa (job #1177616) | Cod sursa (job #2065605)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
struct nod
{
int vecin;
struct nod *urm;
}*l[100003],*L[100003],*actual;
bool viz[100003];
stack<int> stiva;
stack<int> stiva1;
int timp;
void dfs(int k)
{
viz[k]=1;
struct nod *t;
for(t=l[k];t!=NULL;t=t->urm)
{
if(viz[t->vecin]==0)
dfs(t->vecin);
}
stiva.push(k);
stiva1.push(k);
}
void dfs1(int k,bool ok)
{
if(ok)
g<<k<<" ";
viz[k]=1;
struct nod *t;
for(t=L[k];t!=NULL;t=t->urm)
{
if(viz[t->vecin]==0){
dfs1(t->vecin,ok);
}
}
}
int main()
{
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
f>>x>>y;
actual=new nod;
actual->vecin=y;
actual->urm=l[x];
l[x]=actual;
actual=new nod;
actual->vecin=x;
actual->urm=L[y];
L[y]=actual;
}
dfs(1);
for(int i=1;i<=n;i++)
viz[i]=0;
int var;
int sol=0;
bool ok=false;
while(!stiva.empty())
{
var=stiva.top();
if(viz[var]==0){
dfs1(var,ok);
sol++;
}
stiva.pop();
}
for(int i=1;i<=n;i++)
viz[i]=0;
ok=true;
g<<sol<<"\n";
while(!stiva1.empty())
{
var=stiva1.top();
if(viz[var]==0){
dfs1(var,ok);
g<<"\n";
}
stiva1.pop();
}
return 0;
}