Cod sursa(job #900382)

Utilizator bmanghiucManghiuc Bogdan bmanghiuc Data 28 februarie 2013 19:24:41
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <cstdio>
using namespace std;
int N,M,v1[200001][3],coada[100001][2];
bool ps[100001],ms[100001],viz[100001],viz2[100001];
void citire()
{
    int i;
    scanf("%d %d", &N, &M);
    for(i=1;i<=M;i++)
        scanf("%d %d",&v1[i][1], &v1[i][2]);
}
void DFS1(int k)
{
    int i;
     ps[k]++;
    for(i=1;i<=M;i++)
        if(v1[i][1]==k && ps[v1[i][2]]==0)
            DFS1(v1[i][2]);
}
void DFS2(int k)
{
    int i;
     ms[k]++;
    for(i=1;i<=M;i++)
        if(v1[i][2]==k && ms[v1[i][1]]==0)
            DFS2(v1[i][1]);
}
void ctc()
{
    int i,j,x=0,t=0;
        for(i=1;i<=N;i++)
            if(viz[i]==0)
            {
                DFS1(i);
                DFS2(i);
                for(j=1;j<=N;j++)
                    if(ps[j]==1 && ms[j]==1)
                        {
                            viz[j]=1;
                            coada[++x][0]=j;
                        }
                coada[x][1]=1;
                for(j=1;j<=N;j++)
                {
                    ps[j]=0;
                    ms[j]=0;
                }
                t++;
            }

    printf("%d\n" ,t);
}
void afis()
{
    int i=0;
    while(i<N)
    {
        do{
            i++;
            printf("%i " ,coada[i][0]);
        }while(coada[i][1]==0);
            printf("\n");
    }
}
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    citire();
    ctc();
    afis();
    return 0;
}