Cod sursa(job #3164729)

Utilizator christalknightChristian Micea christalknight Data 4 noiembrie 2023 10:37:34
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax = 100003;
int n, m, index;
int viz[nmax];
vector <int> g[nmax];
vector <int> gTranspus[nmax];
vector <int> ctc[nmax];

void dfs(int nod);
void dfsTranspus(int nod);
void read(void);
void reset(void);

int main(){
    int i, j;

    read();

    for(i = 1; i <= n; i++){
        if(viz[i] != 2){
            dfs(i);
            dfsTranspus(i);
            reset();
            index++;
            }
        }
    
    fout<<index<<"\n";
    for(i = 0; i < index; i++){
        for(j = 0; j < ctc[i].size(); j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
        }
    }

void read(void){
    int i, j;
    
    fin>>n>>m;

    while(m--){
        fin>>i>>j;
        g[i].push_back(j);
        gTranspus[j].push_back(i);
        }
    }

void dfs(int nod){
    int i, vecin;

    viz[nod]++;

    for(i = 0; i < g[nod].size(); i++){
        vecin = g[nod][i];

        if(!viz[vecin])
            dfs(vecin);
        }
    }

void dfsTranspus(int nod){
    int i, vecin;

    viz[nod]++;
    ctc[index].push_back(nod);

    for(i = 0; i < gTranspus[nod].size(); i++){
        vecin = gTranspus[nod][i];

        if(viz[vecin] == 1)
            dfsTranspus(vecin);
        }
    }

void reset(void){
    int i;
    
    for(i = 1; i <= n; i++)
        if(viz[i] != 2)
            viz[i] = 0;
    }