Cod sursa(job #3252935)

Utilizator laura2020Moldovan Laura laura2020 Data 31 octombrie 2024 15:58:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define dim 100005
bool fr[dim];
void dfs(int nod,vector<vector<int>>& g,vector<int>& adaugam)
{
    fr[nod]=1;
    for(auto y:g[nod])
    {
        if(fr[y]==0)
            dfs(y,g,adaugam);
    }
    adaugam.push_back(nod);
}

void Solve()
{
    int n,m,i;
    fin>>n>>m;
    vector<vector<int>> g(n);
    vector<vector<int>> gt(n);
    vector<int> st;
    vector<vector<int>> ctc;
    for(i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        x--;y--;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int nod=0;nod<n;nod++)
    {
        if(fr[nod]==0)
        {
            dfs(nod,g,st);
        }
    }
    for(i=0;i<n;i++)
        fr[i]=0;
    for(i=n-1;i>=0;i--)
    {
        int nod=st[i];
        if(fr[nod]==0)
        {
            ctc.resize(ctc.size()+1);
            dfs(nod,gt,ctc.back());
        }
    }
    fout<<ctc.size()<<'\n';
    for(i=0;i<ctc.size();i++)
    {
        sort(ctc[i].begin(),ctc[i].end());
        for(auto j:ctc[i])
            fout<<j+1<<" ";
        fout<<endl;
    }
}

int main()
{
    Solve();
    return 0;
}