Cod sursa(job #707953)

Utilizator freakingVlad Eu freaking Data 6 martie 2012 09:47:01
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#define nmax 200000
using namespace std;
vector <int> pre[nmax],suc[nmax];
int prev[nmax],sucv[nmax];
int viz[nmax];
int n,m;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> stiv[nmax];

void dfsp(int a,int ma)
{
    prev[a]=ma;
    vector <int>::iterator it;
    for(it=pre[a].begin();it!=pre[a].end();it++)
    {
        if(prev[*it]==0)
        {
            dfsp(*it,ma);
        }
    }
}

void dfss(int a,int ma)
{
    sucv[a]=ma;
    vector <int>::iterator it;
    for(it=suc[a].begin();it!=suc[a].end();it++)
    {
        if(sucv[*it]==0)
        {
            dfss(*it,ma);
        }
    }
}



void citire()
{
    int i,j,k;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>j>>k;
        suc[j].push_back(k);
        pre[k].push_back(j);
    }
}

int main()
{
    int ma=0,i,j;
    citire();
    for(i=1;i<=n;i++)
    {
        if(prev[i]==0)
        {
            ma++;
            dfsp(i,ma);
            dfss(i,ma);
            for(j=1;j<=n;j++)
            if(prev[j]!=sucv[j])
            {
                prev[j]=0;
                sucv[j]=0;
            }
            else
            if(ma==prev[j])
                stiv[ma].push_back(j);
        }
    }
    vector<int>::iterator it;
    out<<ma;
    for(i=1;i<=ma;i++)
    {
        out<<"\n";
        for(it=stiv[i].begin();it!=stiv[i].end();it++)
        {
            out<<*it<<" ";
        }
    }

}