bottom.cc.txt

Ulm大学2003-2004年竞赛题

// Problem   The Bottom of a Graph
// Algorithm Strongly Connected Components, Topological Sort, DFS
// Runtime   O(|V|+|E|)
// Author    Walter Guttmann
// Date      26.04.2003

#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream in("bottom.in");

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vi::iterator vit;

void dfs_topsort(vvi &adj, vb &used, vi &topsort, int node)
{
  used[node] = true;
  for (vit it = adj[node].begin() ; it != adj[node].end() ; ++it)
    if (!used[*it])
      dfs_topsort(adj, used, topsort, *it);
  topsort.push_back(node);
}

void dfs_scc(vvi &adj, vb &used, vi &scc, int node)
{
  used[node] = true;
  for (vit it = adj[node].begin() ; it != adj[node].end() ; ++it)
    if (!used[*it])
    {
      scc[*it] = scc[node];
      dfs_scc(adj, used, scc, *it);
    }
}

int main()
{
  while (1)
  {
    int v, e;
    in >> v;
    if (v == 0) break;
    assert(1 <= v && v <= 10000);
    vvi adj(v);
    in >> e;
    assert(0 <= e);
    for (int i=0 ; i<e ; i++)
    {
      int from, to;
      in >> from >> to;
      assert(1 <= from && from <= v);
      assert(1 <= to && to <= v);
      adj[from-1].push_back(to-1);
    }
    // Transpose the graph.
    vvi transpose(v);
    for (int i=0 ; i<v ; i++)
      for (vit it = adj[i].begin() ; it != adj[i].end() ; ++it)
        transpose[*it].push_back(i);
    // Sort the nodes in reverse topological order (not a DAG yet).
    vi topsort;
    {
      vb used(v, false);
      for (int i=0 ; i<v ; i++)
        if (!used[i])
          dfs_topsort(adj, used, topsort, i);
      assert((int)topsort.size() == v);
    }
    // Calculate the SCCs.
    vi scc(v);
    {
      vb used(v, false);
      for (int j=v-1 ; j>=0 ; j--)
      {
        int i = topsort[j];
        if (!used[i])
        {
          scc[i] = i;
          dfs_scc(transpose, used, scc, i);
        }
      }
    }
    // Node i represents a strongly connected component if scc[i] == i.
    // The edges between the SCCs in their DAG are not directly available.
    // If an edge leave the SCC, its source is not a sink.
    vb sink(v, true);
    for (int i=0 ; i<v ; i++)
      for (vit it = adj[i].begin() ; it != adj[i].end() ; ++it)
        if (scc[i] != scc[*it])
          sink[scc[i]] = false;
    bool first = true;
    for (int i=0 ; i<v ; i++)
      if (sink[scc[i]])
        if (first)
          first = false, cout << i+1;
        else
          cout << " " << i+1;
    cout << endl;
  }
  return 0;
}