Cod sursa(job #2445316)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 3 august 2019 15:24:41
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
#define N 105

using namespace std;

int n, m, ans;
bool gasit[N];
stack <int> st;
vector <int> L[N], Rev[N], V[N];

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

void DFS1(int nod)
{
    gasit[nod] = 1;
    for (auto next_nod : L[nod])
    {
        if (!gasit[next_nod])
            DFS1(next_nod);
    }

    st.push(nod);
}

void DFS2(int nod)
{
    V[ans].push_back(nod);
    gasit[nod] = 1;
    for (auto next_nod : Rev[nod])
    {
        if (!gasit[next_nod])
            DFS2(next_nod);
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        L[a].push_back(b);
        Rev[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
		if (!gasit[i])
            DFS1(i);
    }

    memset(gasit, 0, N);
    while (!st.empty())
    {
        int nod = st.top();
        st.pop();

        if (!gasit[nod])
        {
            ans++;
            DFS2(nod);
        }
    }

    fout << ans << "\n";

    for (int i = 1; i <= ans; i++)
    {
        for (auto nod : V[i])
            fout << nod << " ";
        fout << "\n";
    }
    return 0;
}