Cod sursa(job #3276241)

Utilizator VespaOlaru Amelia Vespa Data 12 februarie 2025 23:15:13
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
// prob1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>G[100005],GT[100005];
stack<int>S;
vector<int>ctc;
void dfs(int x)
{
    ctc[x]=1;
    for(auto&i:G[x])
        if(ctc[i]==0)
            dfs(i);
    S.push(x);
}
void dfsT(int x,int nrc)
{
    ctc[x]=nrc;
    for(auto&i:GT[x])
        if(ctc[i]==0)
        dfsT(i,nrc);
}


int main()
{
    int n,m;cin>>n>>m;int nr=0;
    ctc=vector<int>(n+1,0);
    for(int i=0;i<m;i++)
    {
        int x,y;cin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(ctc[i]==0)
        dfs(i);
    ctc=vector<int>(n+1,0);
    int nrc=0;
    while(!S.empty())
    {
        int i=S.top();S.pop();
        if(ctc[i]==0)
        {
            dfsT(i,++nrc);
        }
    }

    cout<<nrc<<'\n';
    for(int i=1;i<=nrc;i++)
    {
        for(int j=1;j<=n;j++)
            if(ctc[j]==i)
            cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}