Cod sursa(job #1743357)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 18 august 2016 00:42:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 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 (size_t i = 0; i < components.size(); ++ i) {
        for (size_t 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;
}