Cod sursa(job #2539647)

Utilizator LivcristiTerebes Liviu Livcristi Data 6 februarie 2020 09:18:01
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NUM 105
using namespace std;
ifstream f("ctc.in");
ofstream fout("ctc.out");
vector<int> g[NUM], gt[NUM];
int v[NUM];
int s[NUM];
int n, m, contor, a, b, lng;
void dfs(int k)
{
    v[k] = 1;
    for(int i = 0; i < g[k].size(); ++i)
        if(!v[g[k][i]])
            dfs(g[k][i]);
    s[lng++] = k;
}
void dfsgt(int k, int nod)
{
    v[k] = nod;
    for(int i = 0; i < gt[k].size(); ++i)
        if(!v[gt[k][i]])
            dfsgt(gt[k][i], nod);
}
int main()
{
    f >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        f >> a >> b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }

    for(int i = 1; i <= n; ++i)
        if(!v[i])
            dfs(i);
    for(int i = 1; i <= n; ++i)
        v[i] = 0;

    for(int i = lng - 1; i >= 0; --i)
    {
        if(!v[s[i]])
        {
            contor++;
            dfsgt(s[i], contor);
        }
    }
    fout << contor;
    for(int i = 0; i <= contor; ++i)
    {
        for(int j = 1; j <= n; ++j)
            if(v[j] == i)
                fout << j << " ";
        fout << "\n";
    }
    return 0;
}