Cod sursa(job #3184907)

Utilizator cristianabalcanuCristiana Balcanu cristianabalcanu Data 17 decembrie 2023 12:45:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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];
vector <vector<int> > ans;
stack <int> s;

void dfs(int nod)
{
    vis[nod] = 1;
    for(int i = 0 ; i < g[nod].size() ; i++)
    {
        if(vis[g[nod][i]] == 1)
            continue;
        dfs(g[nod][i]);
    }
    s.push(nod);
}

void dfst(int nod, vector<int> &c)
{
    c.push_back(nod);
    vis[nod] = 1;
    for(int i = 0 ; i < gt[nod].size() ; i++)
    {
        if(vis[gt[nod][i]] == 1)
            continue;
        dfst(gt[nod][i], c);
    }
}

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);
        }
    }
    memset(vis, 0, sizeof(vis));

    while(!s.empty())
    {
        int nod = s.top();
        s.pop();
        if(vis[nod] == 1)
            continue;
        vector <int> c;
        dfst(nod, c);
        ans.push_back(c);
    }
    fout << ans.size() << '\n';
    for(int i = 0 ; i < ans.size() ; i++)
    {
        for(int j = 0 ; j < ans[i].size() ; j++)
        {
            fout << ans[i][j] << ' ';
        }
        fout << '\n';
    }
    return 0;
}