Cod sursa(job #3187907)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 31 decembrie 2023 11:58:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define DIM 100001

using namespace std;

ifstream fin("ctc.in");

ofstream fout("ctc.out");

stack <int> st;

vector <int> G[DIM], GT[DIM], sol[DIM];

int found[DIM];

int n, Q, x, y, i, j, number;

void dfs(int node){

    found[node] = 1;

    for(int i = 0 ; i < G[node].size(); i++)

        if(!found[G[node][i]])

            dfs(G[node][i]);

    st.push(node);

}

void dfst(int node){

    found[node]++;

    sol[number].push_back(node);

    for(int i = 0 ; i < GT[node].size() ; i++)

        if(found[GT[node][i]] == 1)

            dfst(GT[node][i]);

}

int main(){

    fin >> n >> Q;

    while(Q--){

        fin >> x >> y;

        G[x].push_back(y);

        GT[y].push_back(x);

    }

    for(i=1;i<=n;i++)

        if(!found[i])

            dfs(i);

    while(!st.empty()){

        if(found[st.top()] == 1){

            number++;

            dfst(st.top());


        }

        st.pop();

    }

    fout << number << "\n";

    for(i=1;i<=number;i++, fout << "\n")

        for(j=0;j<sol[i].size();j++)

            fout << sol[i][j] << " ";

}