Cod sursa(job #2691489)

Utilizator bubblegumixUdrea Robert bubblegumix Data 28 decembrie 2020 22:30:26
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int> > G, GT,sol;

int n, m, contor, nrs;

vector<bool> V;
vector<int> S;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void read()
{
    fin >> n >> m;
    G = GT = vector<vector<int>>(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

}

void dfs(int k)
{
    V[k] = true;
    for (auto x : G[k])
        if (!V[x])
            dfs(x);
    S.push_back(k);
}

void dfsGT(int k,vector<int> &ST)
{
    V[k] = 1;
    for (auto x : GT[k])
        if (!V[x])
            dfsGT(x,ST);
    ST.push_back(k);

}
void print(vector<int> &s)
{
    for (auto it : s)
        fout << it << " ";
    fout << endl;
}
int main()
{
    read();

    V = vector<bool>(n + 1, false);
    for (int i = 1; i <= n; i++)
        if (!V[i])
        {
            dfs(i);
           // print(S);
        }

    V = vector<bool>(n + 1, false);
    for (vector<int>::reverse_iterator it = S.rbegin(); it != S.rend(); it++)
        if (!V[*it]) {
            contor++;
            vector<int> ST;
            dfsGT(*it,ST);
            sol.push_back(ST);
            
        }

    fout << contor<<endl;
    for (auto it : sol)
        print(it);
    return 0;
}

/*
8 11
1 2
1 3
3 1
3 4
4 1 
4 2
2 5
5 7
6 5
8 6
7 8
*/