Cod sursa(job #2666569)

Utilizator @stefansevastre@Stefan Sevastre @stefansevastre@ Data 2 noiembrie 2020 10:16:56
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, viz[100001], comp;
vector <int> l1[100001],l2[100001],rez[100001];
stack <int> stiva;

void DFS(int node)
{
    viz[node]=1;
    for(int i=0; i<l1[node].size(); i++)
    {
        if(viz[l1[node][i]]==0)
            DFS(l1[node][i]);
    }
    stiva.push(node);
}

void DFS2(int node)
{
    viz[node]=1;
    rez[comp].push_back(node);

    for(int i=0; i<l2[node].size(); i++)
        if (viz[l2[node][i]]==0)
            DFS2(l2[node][i]);
}

int main()
{
    int i,j,k;

    fin>>N>>M;
    for(i=0; i<M; i++)
    {
        fin>>j>>k;
        l1[j].push_back(k);
        l2[k].push_back(j);
    }

    for(i=1; i<=N; i++)
    {
        if(viz[i]==0)
            DFS(i);
    }

    for (i=1; i<=N; i++)
        viz[i]=0;

    while(!stiva.empty())
    {
        int nod=stiva.top();
        if(viz[nod]==0)
        {
            comp++;
            DFS2(nod);
        }
        stiva.pop();
    }

    fout<<comp<<endl;
    for(i=1; i<=comp; i++)
    {
        for(j=0; j<rez[i].size(); j++)
            fout<<rez[i][j]<< " ";
        fout<<endl;
    }

    return 0;
}