Cod sursa(job #2711646)

Utilizator rafaelrafyChitan Rafael rafaelrafy Data 24 februarie 2021 15:34:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int ctc;
list<int>lext,lint;
map<int,int>ge[110000],gi[110000];
bool ok[110000], OK[110000];
int n,m,x,y, nrsol, kmax;
vector<int> solfin[110000];
stack<int> v;
void dfs(int x)
{
    ok[x]=1;
    for(auto &it: ge[x])
        if(!ok[it.first])
            dfs(it.first);
    v.push(x);
}

void dfs2(int x)
{
    solfin[ctc].push_back(x);
    OK[x]=1;
    for(auto &it: gi[x])
        if(!OK[it.first])
            dfs2(it.first);
}
int main() {
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        ge[x][y]=gi[y][x]=1;
    }
    for(int i=1;i<=n;i++)
        if(!ok[i])
            dfs(i);
    
    while(!v.empty())
    {
        x=v.top();
        if(!OK[x])
        {
            ctc++;
            dfs2(x);
            sort(solfin[ctc].begin(), solfin[ctc].end());
        }
        v.pop();
    }
    g<<ctc<<'\n';
    for(int i=1;i<=ctc;i++)
    {
        for(auto &j: solfin[i])
            g<<j<<' ';
        g<<'\n';
    }
    return 0;
}