Cod sursa(job #526946)

Utilizator icepowdahTudor Didilescu icepowdah Data 29 ianuarie 2011 23:36:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <stack>
using namespace std;

#define NMAX 100000

struct list {
  int id;
  list* next;
};

int N, M;
bool visited[NMAX+1];
list* adj_list[NMAX+1];
list* adj_list_inverted[NMAX+1];
list* ctc_list[NMAX+1];
stack<int> stiva;
int ctc_count = 0;

void readInput();
void dfs(int s);
void dfsT(int s);

int main(void)
{
  readInput();

  for (int i=1;i<=N;i++)
  {
    if (!visited[i])
      dfs(i);
  }

  for (int i=1;i<=N;i++)
    visited[i] = false;

  while (!stiva.empty())
  {
    int v = stiva.top();
    stiva.pop();
    if (!visited[v])
    {
      ctc_count++;
      dfsT(v);
    }
  }

  ofstream g("ctc.out");
  g << ctc_count << "\n";
  for (int i=1;i<=ctc_count;i++)
  {
    list* it = ctc_list[i];
    while (it != NULL)
    {
      g << it->id << " ";
      it = it->next;
    }
    g << "\n";
  }

  g.close();
  return 0;
}

void readInput()
{
  int from, to;
  ifstream f("ctc.in");

  f >> N >> M;
  for (int i=1;i<=M;i++)
  {
    f >> from >> to;    
    list* x = new list;
    x->id = to;
    x->next = adj_list[from];
    adj_list[from] = x;

    x = new list;
    x->id = from;
    x->next = adj_list_inverted[to];
    adj_list_inverted[to] = x;
  }

  f.close();
}

void dfs(int s)
{
  visited[s] = true;
  list* it = adj_list[s];
  while (it != NULL)
  {
    if (!visited[it->id])
    {
      dfs(it->id);
    }
    it = it->next;
  }
  stiva.push(s);
}

void dfsT(int s)
{
  visited[s] = true;
  list* it = adj_list_inverted[s];
  while (it != NULL)
  {
    if (!visited[it->id])
    {
      dfsT(it->id);
    }
    it = it->next;
  }

  list* x = new list;
  x->id = s;
  x->next = ctc_list[ctc_count];
  ctc_list[ctc_count] = x;
}