Cod sursa(job #2798519)

Utilizator MihaiBirsanMihai Birsan MihaiBirsan Data 11 noiembrie 2021 14:15:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;


#define Nmax 100010

ifstream fin("ctc.in");
ofstream fout("ctc.out");
//folosim algoritmul Kosaraju
vector<int> g[Nmax];
vector<int> gt[Nmax];//graful transpus
int viz1[Nmax];
int viz2[Nmax];
int comp[Nmax];
vector<int> topo;
int ct=0;
vector<int> ctc[Nmax];

void DFS1(int x)
{
    viz1[x] = 1;
    for(int i = 0; i < g[x].size(); i++) //vecinii nodului curent
    {
        if(viz1[g[x][i]] == 0)
            DFS1(g[x][i]);
    }
    topo.push_back(x);
}

void DFS2(int x)
{
    viz2[x] = 1;
    comp[x] = ct;
    ctc[ct].push_back(x);
    for(int i = 0; i< gt[x].size(); i++)
    {
        if(viz2[gt[x][i]] == 0)
        {
            DFS2(gt[x][i]);
        }
    }
}


int main()
{
    int n,m,x,y;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(int i=1;i<=n;++i)
    {
        if(viz1[i] == 0)
        {
            DFS1(i);
        }
    }
    reverse(topo.begin(), topo.end());
    for(auto i:topo)
    {
        if(comp[i] == 0)
        {
            ct += 1;
            DFS2(i);
        }
    }

    fout << ct << '\n';
    for(int i = 1; i <= ct; i++)
    {
        for(auto j:ctc[i])
            fout << j << ' ';
        fout << '\n';
    }


    return 0;
}