Cod sursa(job #1344070)

Utilizator varga13VarGaz13 varga13 Data 16 februarie 2015 12:14:37
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#define mx 100000
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> G[mx];
vector<int> Gt[mx];
vector<int> Sol[mx];
int color[mx],m,n;

void Read()
{
    f>>n>>m;
    for(int i=0;i<m;++i)
    {
        int from,to;
        f>>from>>to;
        G[from].push_back(to);
        Gt[to].push_back(from);
    }
}

void DFS(int start)
{
    color[start]=1;
    for(int i=0;i<G[start].size();i++)
    {
        if(color[G[start][i]]==0)
        {
            DFS(G[start][i]);
        }
    }
}

void DFSt(int start)
{
    color[start]=2;
    for(int i=0;i<Gt[start].size();i++)
    {
        if(color[Gt[start][i]]==1)
        {
            DFSt(Gt[start][i]);
        }
    }
}
int k;
int main()
{

    Read();

    for(int i=1;i<=n;i++)
    {
        if((color[i]!=2)&&(color[i]!=-1))
        {
            DFS(i);
            DFSt(i);
            k++;
            for(int j=1;j<=n;j++)
            {
                if(color[j]==2)
                    Sol[k].push_back(j);
            }
            for(int j=1;j<=n;j++)
            {
                if(color[j]==1)
                    color[j]=0;
                if(color[j]==2)
                    color[j]=-1;
            }
        }

    }
    g<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<Sol[i].size();j++)
            g<<Sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}