Cod sursa(job #1491521)

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

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

vector<vector<int> > sol;

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); }
        }
    }
    ctc.clear();
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==1 && viz2[i]==2) { ctc.pb(i); used[i]=1;}
        viz[i]=0; viz2[i]=0;
    }
    sol.pb(ctc);
    nrcomp++;
}

int main()
{
    int n1,n2,i,j;
    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);
    printf("%d\n",nrcomp);
    for( i=0;i<sol.size();i++)
    { for(j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]); printf("\n"); }
    fclose(stdin);
    fclose(stdout);
    return 0;
}