Cod sursa(job #2816184)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 11 decembrie 2021 10:32:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> h[100003];
vector <int> g[100003];
vector <int> scc[100003]; /// strongly conn. comp.

int n, m, nrc;
int st[100003], viz[100003], top;

void DFS(int n)
{
    viz[n] = 1;
    for (int i : h[n])
        if (viz[i] == 0)
            DFS(i);
    st[++top] = n;
}


/// viz[i] = 1 , pt orice i de la 1 la n, astfel consideram viz[i] = 1 -> nevizitat
/// viz[i] = 0 -> vizitat, pentru a nu reinitializa vectorul viz
void DFS2(int n)
{
    viz[n] = 0;
    for (int i : g[n])
        if (viz[i] == 1)
            DFS2(i);
    scc[nrc].push_back(n);
}

void SCC()
{
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            DFS(i);
    for (int i = n; i > 0; i--)
        if (viz[st[i]] == 1)
        {
            nrc++;
            DFS2(st[i]);
        }
}

void Afis()
{
    fout << nrc << "\n";
    for (int i = 1; i <= nrc; i++)
    {
        for (int j : scc[i])
            fout << j << " ";
        fout << "\n";
    }
}



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