Cod sursa(job #3254604)

Utilizator LolluckestarNastasa-Baras Luca Lolluckestar Data 8 noiembrie 2024 09:50:54
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int viz[100002];
vector<int> Ad[100002];
vector<int> AdT[100002];
stack<int> S;

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

void dfs(int x){
    viz[x] = 1;
    for(auto node:Ad[x]){
        if(viz[node]!=1){
            dfs(node);
        }
    }
    S.push(x);
}

void kosDfs(int x,int k){
    viz[x] = k;
    for(auto node:AdT[x]){
        if(viz[node]==0){
            kosDfs(node,k);
        }
    }
}


int main()
{
    int n,m,l,k;
    fin>>n>>m;

    for(int i = 0;i<m;i++){
        fin>>l>>k;
        l--;
        k--;
        Ad[l].push_back(k);
        AdT[k].push_back(l);
    }

    for(int i = 0 ;i<n;i++){
        if(viz[i]!=1){
            dfs(i);
        }
    }
    int nr =0;
    for(int i = 0;i<n;i++){
        viz[i]=0;
    }
    while(!S.empty()){
        int nod = S.top();
        S.pop();
        if(viz[nod] != 0){
            continue;
        }
        nr++;
        kosDfs(nod,nr);
    }
    fout<<nr<<'\n';
for(int j = 0;j<nr;j++)
    {
        for(int i = 0 ;i<n;i++){
            if(viz[i] == j+1){
                fout<<i+1<<' ';
            }
        }
        fout<<'\n';
    }
}