Cod sursa(job #1638030)

Utilizator daGramaGrama Matei daGrama Data 7 martie 2016 20:41:31
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
using namespace std;

#define N  100000

ifstream f("ctc.in");
ofstream g("ctc.out");

int lst3[]

int lst1[N],lst2[N], vf1[N],vf2[N],urm1[N],urm2[N],nr,n,m;
bool viz1[N], viz2[N];
int c[N],nc;
int v[N],nv;

void adauga(int x,int y){
    nr++;
    vf1[nr]=y;
    urm1[nr]=lst1[x];
    lst1[x]=nr;
}
void adauga2(int x,int y){
    nr++;
    vf2[nr]=y;
    urm2[nr]=lst2[x];
    lst2[x]=nr;
}
void dfs1(int x)
{
    int y,p;
    viz1[x] = true;
    p=lst1[x];
    while(p!=0){
        y=vf1[p];
        if(!viz1[y])
            dfs1(y);
        p=urm1[p];
    }
    c[++nc]=x;
}
int dfs2(int x)
{
    int y,p;
    viz2[x] = true;
    p=lst2[x];
    while(p!=0){
        y=vf2[p];
        if(!viz2[y])
            dfs2(y);
        p=urm2[p];
    }
}
int main()
{
    int x,y;
    f>>n>>m;
    for(int i=1; i<=m; i++){
        f>>x>>y;
        adauga(x, y);
        adauga2(y, x);
    }
    for(int i=1;i<=n;i++){
        if(!viz1[i]){
            dfs1(i);
        }
    }
    im=1;
    for(int i=n;i>=1;i--){
        dfs2(c[i]);
    }


    return 0;
}