Cod sursa(job #3263896)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 16 decembrie 2024 21:25:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define VMAX 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector<int> graf[VMAX];
vector<int> graf_invers[VMAX];
bool vizitat[VMAX];
int timp=0,nrc=0;
int postordine[VMAX];
vector<int> ctc[VMAX];

void dfs(int nod)
{
    vizitat[nod]=1;
    for(auto it:graf[nod])
    {
        if(vizitat[it]==0)
            dfs(it);
    }
    postordine[timp++]=nod;
}


void dfs_pe_inv(int nod)
{
    vizitat[nod]=0;
    ctc[nrc].push_back(nod);
    for(auto it:graf_invers[nod])
    {
        if(vizitat[it])
        {
            dfs_pe_inv(it);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k;
        graf[j].push_back(k);
        graf_invers[k].push_back(j);
    }


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

    for(i=n;i>=0;i--)
    {
        if(vizitat[postordine[i]]!=0)
        {
            nrc++;
            dfs_pe_inv(postordine[i]);
        }
    }

    fout<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(j=0;j<ctc[i].size();j++)
            fout<<ctc[i][j]<<' ';
        fout<<'\n';
    }


    return 0;
}