Cod sursa(job #2150396)

Utilizator raluvladRaluca Vlad raluvlad Data 3 martie 2018 15:29:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>

using namespace std;

vector <int> g1[100005],g2[100005],c[100005];
int use[100005],ct=0,n,m;

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

void Read()
{
    int i,x,y;
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        g1[x].push_back(y);
        g2[y].push_back(x);
    }
}

void DFS1(int nod)
{
    use[nod]=1;
    for(unsigned int i=0;i<g1[nod].size();i++)
    {
        int vecin = g1[nod][i];
        if(!use[vecin])
            DFS1(vecin);
    }
}

void DFS2(int nod)
{
    use[nod]=2;
    c[ct].push_back(nod);
    for(unsigned int i=0;i<g2[nod].size();i++)
    {
        int vecin = g2[nod][i];
        if(use[vecin] == 1)
            DFS2(vecin);
    }
}

int main()
{
    int i,j;
    Read();
    for(i=1;i<=n;i++)
        if(use[i]==0)
        {
            DFS1(i);
            DFS2(i);
            ct++;

            for(j=1;j<=n;j++)
                if(use[j]==1)
                    use[j]=0;
        }
    out<<ct<<'\n';
    for(i=0;i<ct;i++)
    {
        for(j=0; j<c[i].size();j++)
            out<<c[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}