Cod sursa(job #1491504)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 25 septembrie 2015 16:35:12
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>
#include <stack>
#define nmax 100010
#define pb push_back
using namespace std;

int n,m;
vector<int> d[nmax],r[nmax];
int viz[nmax],viz2[nmax],used[nmax];
stack<int> s;

void parc(int x)
{
    int i,nod;
    vector<int>::iterator it;
    s.push(x); viz[x]=1;
    while(!s.empty())
    {
        nod=s.top(); s.pop();
        for(it=d[nod].begin();it!=d[nod].end();it++)
        {
            if(!viz[*it]) { viz[*it]=1; s.push(*it); }
        }
    }

    s.push(x); viz2[x]=2;
    while(!s.empty())
    {
        nod=s.top(); s.pop();
        for(it=r[nod].begin();it!=r[nod].end();it++)
        {
            if(!viz2[*it]) { viz2[*it]=2; s.push(*it); }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==1 && viz2[i]==2) { printf("%d ",i); used[i]=1;}
        viz[i]=0; viz2[i]=0;
    }
    printf("\n");
}

int main()
{
    int n1,n2,i;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d",&n1,&n2);
        d[n1].pb(n2);
        r[n2].pb(n1);
    }
    for(i=1;i<=n;i++)
        if(!used[i]) parc(i);
    fclose(stdin);
    fclose(stdout);
    return 0;
}