Cod sursa(job #1743265)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 17 august 2016 20:52:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define MAX_NODES 100100

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

vector <int> graph[MAX_NODES];
vector <int> reversed_graph[MAX_NODES];
vector <int> components[MAX_NODES];
int dfs_time[MAX_NODES];
bool visited[MAX_NODES];
bool tarjan_visited[MAX_NODES];
int no_of_nodes;
int no_of_edges;
int number_of_components = 0;
int time_in = 0;

void dfs(int node) {
  visited[node] = true;
  for (int neighbor = 0; neighbor < graph[node].size(); neighbor++) {
    if(visited[graph[node][neighbor]] == false) {
      dfs(graph[node][neighbor]);
    }
  }

  dfs_time[++time_in] = node;
}

void dfs_tarjan(int node) {
  tarjan_visited[node] = true;
  components[number_of_components].push_back(node);
  for(int i=0; i<reversed_graph[node].size(); ++i) {
    if (tarjan_visited[reversed_graph[node][i]] == false ) {
      dfs_tarjan(reversed_graph[node][i]);
    }
  }
}

void tarjan() {
  for(int node = 1; node <= no_of_nodes; node++) {
    if(visited[node] == false) {
      dfs(node);
    }
  }

  for (int node = no_of_nodes; node > 0; node--) {
    if (tarjan_visited[dfs_time[node]] == false) {
      number_of_components++;
      dfs_tarjan(dfs_time[node]);
    }
  }
}

void print_solution() {
  fout<<number_of_components<<'\n';

  for (int component_index=1; component_index <= number_of_components; component_index++) {
    for (int node_index = 0; node_index < components[component_index].size(); node_index++) {
      fout<<components[component_index][node_index]<<' ';
    }
    fout<<'\n';
  }
}

void init_data() {
  for (int index = 0; index <= no_of_nodes; index++) {
    visited[index] = false;
    tarjan_visited[index] = false;
  }
}

void read_data() {
  int node1, node2;
  fin>>no_of_nodes;
  fin>>no_of_edges;

  for (int index = 1; index <= no_of_edges; index++) {
    fin>>node1>>node2;
    graph[node1].push_back(node2);
    reversed_graph[node2].push_back(node1);
  }
}

int main() {
    read_data();
    init_data();
    tarjan();
    print_solution();

    return 0;
}