Cod sursa(job #2065605)

Utilizator sotoc1999Sotoc George sotoc1999 Data 13 noiembrie 2017 22:36:37
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#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;
}