Cod sursa(job #2721507)

Utilizator danhHarangus Dan danh Data 11 martie 2021 21:26:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMAX =  100005;

vector<int> po;

vector<int> g[NMAX], gt[NMAX];
vector<int> comps[NMAX];

bitset<NMAX> viz;

int c;

void dfs(int x)
{
    viz[x] = 1;
    for(int nod : g[x])
    {
        if(!viz[nod])
        {
            dfs(nod);
        }
    }
    po.push_back(x);
}

void dfst(int x)
{
    comps[c].push_back(x);
    viz[x] = 0;
    for(int nod : gt[x])
    {
        if(viz[nod])
        {
            dfst(nod);
        }
    }
}

int main()
{
    int n, m, i, j, x, y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            dfs(i);
        }
    }

    for(i=po.size()-1; i>=0; i--)
    {
        if(viz[po[i]])
        {
            c++;
            dfst(po[i]);
        }
    }

    fout<<c<<'\n';
    for(i=1; i<=n; i++)
    {
        for(int el : comps[i])
        {
            fout<<el<<' ';
        }
        fout<<'\n';
    }

}