Cod sursa(job #2816195)

Utilizator CraiuAndreiCraiu Andrei David CraiuAndrei Data 11 decembrie 2021 10:33:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb

#include <bits/stdc++.h>
using namespace std;

/**
Componente tare conexe (Strong connected)
{1}
Un digraf este tare conex daca exista drum intre oricare
doua noduri.
*/
vector<int> h[100003]; /// liste ad.
vector<int> g[100003]; /// liste ad. pe arce inverse
vector<int> ctc[100003]; /// componentele tare conexe
int n, m, nrc;
int st[100003], top;
int viz[100003];
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void Citire()
{
    int i, j;
    fin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        fin >> i >> j;
        h[i].push_back(j);
        g[j].push_back(i);
    }
}

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

/// Acum viz[i]=1 inseamna nevizitat si
///      viz[i]=0 inseamna vizitat
void DFS(int k)
{
    viz[k] = 0;
    for (int i : g[k])
        if (viz[i] == 1) DFS(i);
    ctc[nrc].push_back(k);
}

void ConstrCTC()
{
    int i;
    /// sortare topologica
    for (i = 1; i <= n; i++)
        if (viz[i] == 0)
            DFSF(i);
    /// determinare c.t.c
    for (i = n; i >= 1; i--)
        if (viz[st[i]] == 1)
        {
            nrc++;
            DFS(st[i]);
        }
}

void Afisare()
{
    fout << nrc << "\n";
    for (int i = 1; i <= nrc; i++)
    {
        ///sort(ctc[i].begin, ctc[i].end());
        for (int j : ctc[i])
            fout << j << " ";
        fout << "\n";
    }
}

int main()
{
    Citire();
    ConstrCTC();
    Afisare();
    fin.close();
    fout.close();
    return 0;
}