Cod sursa(job #1618237)

Utilizator hackerliAndrei Ion hackerli Data 27 februarie 2016 19:02:59
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int a[10000][10000], n, m, x, y, viz[10000], sol[10000][10000];
/**
1 = +
2 = -
3 = +/-
4 = sters
**/
void dfplus(int t)
{
    viz[t]=1;
    for(int i=1; i<=n; i++)
    {
        if(a[t][i]==1&&viz[i]==0)
        {
            viz[i]=1;
            dfplus(i);
        }
    }
}
void dfminus(int t)
{
    int ok=0;
    if(viz[t]==0)
    {
        viz[t]=2;
        ok=1;
    }
    else if(viz[t]==1)
    {
        viz[t]=3;
        ok=1;
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i][t]==1&&ok==1)
        {
            dfminus(i);
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        a[x][y]=1;
    }
    int t=1;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]!=4)
        {
            dfplus(i);
            dfminus(i);
            int k=1;
            for(int j=1; j<=n; j++)
            {
                if(viz[j]==3)
                {
                    sol[t][k]=j;
                    sol[t][0]++;
                    k++;
                    viz[j]=4;
                }
                else if(viz[j]!=4)
                {
                    viz[j]=0;
                }
            }
            t++;
        }
    }
    t--;
    fout<<t<<'\n';
    for(int i=1; i<=t; i++)
    {
        for(int j=1; j<=sol[i][0]; j++)
        {
            fout<<sol[i][j]<<' ';
        }
        fout<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}