Cod sursa(job #2166485)

Utilizator eduardvintilaVintila Eduard eduardvintila Data 13 martie 2018 17:23:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

int n,viz[100005];

vector<int> v[100005],v2[100005];
vector< vector<int> > ctc;
stack<int> stiva;

void DFS1(int x)
{
    viz[x]=1;
    for (size_t i=0; i<v[x].size(); i++)
    {
        if (viz[v[x][i]]==0)
            DFS1(v[x][i]);
    }
    stiva.push(x);
}

void DFS2(int x, vector<int> &comp)
{
    viz[x]=1;
    comp.emplace_back(x);
    for (size_t i=0; i<v2[x].size(); i++)
    {
        if (viz[v2[x][i]]==0)
            DFS2(v2[x][i],comp);
    }
}

int main()
{
    int i,x,y,m,j,nr=0;
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].emplace_back(y);
        v2[y].emplace_back(x);
    }
    for (i=1; i<=n; i++)
    {
        if (viz[i]==0)
            DFS1(i);
    }
    for (i=1; i<=n; i++)
        viz[i]=0;
    while (stiva.empty()==0)
    {
        x=stiva.top();
        stiva.pop();
        if (viz[x]==0)
        {
            vector<int> comp;
            DFS2(x,comp);
            ctc.push_back(comp);
            nr++;
        }
    }
    g<<nr<<'\n';
    for (i=0;i<nr;i++)
    {
        for (j=0;j<ctc[i].size();j++)
            g<<ctc[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}