Cod sursa(job #2678675)

Utilizator raducostacheRadu Costache raducostache Data 28 noiembrie 2020 14:58:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
//
//  main.cpp
//  ctc
//
//  Created by Radu Costache on 28/11/2020.
//  Copyright © 2020 Radu Costache. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <cstring>
#include <stack>


#define NMAX 100005

using namespace std;

int n, m, ctc;

stack <int> st;

vector <int> v1[NMAX];
vector <int> v2[NMAX];
vector <int> ans[NMAX];
vector<int> comp;

void dfs1(int);
void dfs2(int);

bool viz[NMAX], viz1[NMAX], viz2[NMAX];


int main(int argc, const char * argv[]) {
    // insert code here...
    FILE *f = fopen("ctc.in","r");
    FILE *g = fopen("ctc.out", "w");
    fscanf(f, "%d %d\n", &n, &m);
    while (m--) {
        int x, y;
        fscanf(f, "%d %d\n", &x, &y);
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i) {
        if (!viz1[i]) {
            dfs1(i);
        }
    }
    
    while (!st.empty()) {
        if (!viz2[st.top()]) {
            ++ctc;
            dfs2(st.top());
        }
        st.pop();
    }
    fprintf(g, "%d\n",ctc);
    for (int i = 1; i <= ctc; ++i) {
        for (auto it:ans[i])
            fprintf(g, "%d ", it);
        fprintf(g, "\n");
    }
    return 0;
}

void dfs1(int node) {
    viz1[node] = 1;
    for (auto it:v1[node])
        if (viz1[it] == 0) {
            dfs1(it);
        }
    st.push(node);
}

void dfs2(int node) {
    viz2[node] = 1;
    ans[ctc].push_back(node);
    
    for (auto it:v2[node])
        if (viz2[it] == 0) {
            dfs2(it);
        }
}