Cod sursa(job #2678627)

Utilizator raducostacheRadu Costache raducostache Data 28 noiembrie 2020 14:31:56
Problema Componente tare conexe Scor 60
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>


#define NMAX 100005

using namespace std;

int n, m, ctc;

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

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 (!viz[i]) {
            ++ctc;
            memset(viz1, 0, sizeof(viz1));
            dfs1(i);
            memset(viz2, 0, sizeof(viz2));
            dfs2(i);
        }
    }
    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 && viz[it] == 0) {
            dfs1(it);
        }
}

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