Cod sursa(job #3184889)

Utilizator cristianabalcanuCristiana Balcanu cristianabalcanu Data 17 decembrie 2023 12:28:03
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define NN 100005
#define MM 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

int n, m, a, b, nrc, vis[NN];
vector <int> g[NN], gt[NN];
int z[NN], nz;

void dfs(int x)
{
    int y;
    vis[x] = 1;
    for(int i = 0 ; i < g[x].size() ; i++)
    {
        y = g[x][i];
        if(vis[y] == 0)
        {
            dfs(y);
        }
    }
    nz++;
    z[nz] = x;
}

void dfst(int x)
{
    int y;
    vis[x] = nrc;
    for(int i = 0 ; i < gt[x].size() ; i++)
    {
        y = gt[x][i];
        if(vis[y] == 0)
        {
            dfst(y);
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> a >> b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(vis[i] == 0)
        {
            dfs(i);
        }
    }
    for(int i = 1 ; i <= n ; i++)
        vis[i] = 0;
    for(int i = nz ; i > 0 ; i--)
    {
        if(vis[z[i]] == 0)
        {
            nrc++;
            dfst(z[i]);
        }
    }
    fout << nrc << '\n';
    for(int i = 1 ; i <= nrc ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            if(vis[j] == i)
                fout << j << ' ';
        }
        fout << '\n';
    }
    return 0;
}