Cod sursa(job #1569495)

Utilizator dinu_sergiuDinu Sergiu Andrei dinu_sergiu Data 15 ianuarie 2016 17:19:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <stack>

#define nmax 100001


using namespace std;

FILE *f=fopen("ctc.in", "r");
FILE *g=fopen("ctc.out", "w");

struct nod
{
    int info;
    nod *urm;
}*prim[nmax], *primt[nmax];

inline void Addnod(int x, int y)
{
    nod *p=new nod;
    p->info=y;
    p->urm=prim[x];
    prim[x]=p;

    nod *q=new nod;
    q->info=x;
    q->urm=primt[y];
    primt[y]=q;
}

bool viz[100001], vizt[100001];
int n, m;
stack <int> S;
stack <int> St;


void Citire()
{
    int i, x, y;
    fscanf(f, "%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(f, "%d%d", &x, &y);
        Addnod(x, y);
    }
}

void DFS(int x)
{
    viz[x]=1;
    for(nod *p=prim[x]; p!=NULL; p=p->urm)
        if(viz[p->info]==0)
            DFS(p->info);
    S.push(x);
}

void DFSt(int x)
{
    vizt[x]=1;
    for(nod *p=primt[x]; p!=NULL; p=p->urm)
        if(vizt[p->info]==0)
            DFSt(p->info);
    St.push(x);
}

void Sol()
{
    int i, x, nr=0;
    for(i=1; i<=n; i++)
        if(viz[i]==0)
            DFS(i);
    while(!S.empty())
    {
        x=S.top();
        S.pop();
        if(vizt[x]==false)
        {
            St.push(-1);
            DFSt(x);
            nr++;
        }
    }
    fprintf(g, "%d\n", nr);
    while(!St.empty())
    {
        x=St.top();
        St.pop();
        if(x==-1)
            fprintf(g, "\n");
        else
           fprintf(g, "%d ", x);
    }
}

int main()
{
    Citire();
    Sol();
    fclose(f);
    fclose(g);
    return 0;
}