Cod sursa(job #2781115)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 8 octombrie 2021 15:14:35
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb

#include <bits/stdc++.h>

#include <fstream>

#define VMAX 100000

#define EMAX 200000

using namespace std;



ifstream fin("ctc.in");

ofstream fout("ctc.out");



vector <int> adj[VMAX];

vector <int> aux[VMAX];

vector <int> component;

vector <int> toate[EMAX];



int V, E, x, y;

stack <int> st;

bool vis[VMAX];



void DFS(int u)

{

    vis[u] = true;

    for (auto w:adj[u])

        if (!vis[w]) DFS(w);

    st.push(u);

}



void DFS_2(int u, int contor)

{

    vis[u] = true;

    toate[contor].push_back(u);

    for (auto w:aux[u])

        if (!vis[w]) DFS_2(w, contor);

}



int main()

{

    ios_base::sync_with_stdio(false);

    fin.tie(NULL);

    fout.tie(NULL);



    fin >> V >> E;



    for (int i = 0; i < E; i++)

    {

        fin >> x >> y;

        x--, y--;

        adj[x].push_back(y);

        aux[y].push_back(x);

    }



    for (int i = 0; i < V; i++)

        if (vis[i] == false) DFS(i);



    for (int i = 0; i < V; i++)

        vis[i] = false;



    int nr = 0, contor = 0;



    while (!st.empty())

    {

        if (vis[st.top()] == false)

        {

            DFS_2(st.top(), contor);

            contor++;

        }

        st.pop();

    }



    fout << contor << endl;



    for (int i = 0; i < contor; i++)

    {

        for (auto elem:toate[i])

            fout << elem + 1 << " ";

        fout << endl;

    }



    fin.close();

    fout.close();

    return 0;

}