Cod sursa(job #1743358)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 18 august 2016 00:48:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

#define MAXN  100005

vector <int> graph[MAXN];
vector<int> new_component, dfs_time, lowlink, in_stack;

vector <vector<int> > components;

stack <int> Stack;

int dfs_time_node_index, nodes_count;

int min (int a, int b) {
  if (a < b) {
    return a;
  }

  return b;
}

void read_data() {
  ifstream in("ctc.in");

  int edges_count;
  int node1;
  int node2;

  in >> nodes_count;
  in >> edges_count;

  for (; edges_count > 0; -- edges_count) {
    in >> node1;
    in >> node2;
    graph[node1 - 1].push_back(node2 - 1);
  }
}

void print_data() {
    ofstream out("ctc.out");
    out << components.size() << "\n";
    for (int i = 0; i < components.size(); ++ i) {
        for (int j = 0; j < components[i].size(); ++ j) {
            out << components[i][j] + 1 << " ";
        }
        out << "\n";
    }
}

void recursive_tarjan(int n)
{
    dfs_time[n] = lowlink[n] = dfs_time_node_index;
    dfs_time_node_index ++;
    Stack.push(n);
    in_stack[n] = 1;

    for (int i = 0; i < graph[n].size(); ++ i) {
        int node = graph[n][i];
        if (dfs_time[node] == -1) {
            recursive_tarjan(node);
            lowlink[n] = min(lowlink[n], lowlink[node]);
        }
        else if (in_stack[node]) {
            lowlink[n] = min(lowlink[n], lowlink[node]);
        }
    }

    if (dfs_time[n] == lowlink[n]) {
        new_component.clear();
        int node;
        do {
            new_component.push_back(node = Stack.top());
            Stack.pop(), in_stack[node] = 0;
        }
        while (node != n);
        components.push_back(new_component);
    }
}

void tarjan_algorithm() {
  for (int i = 0; i < nodes_count; ++ i) {
    if (dfs_time[i] == -1) {
      recursive_tarjan(i);
    }
  }
}

void init_data() {
  lowlink.resize(nodes_count);

  for (int i = 0; i < nodes_count; i++) {
    dfs_time.push_back(-1);
    in_stack.push_back(0);
  }
}

int main(void)
{
    read_data();
    init_data();
    tarjan_algorithm();
    print_data();
    return 0;
}