BZOJ2030

找割点
对于一个只包含一个割点的块
要有一个出口 可以在这个块中任意不是割点的点上
而对于 有两个割点的块则不需要割点
有一个地方要特判 没有割点 要两个出口

第一次打tarjan = =
就当贴个模板吧。。
—————————————————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
using namespace std;
typedef long long ll;
const int maxn = 505;
struct line
{
  int next, to;
}li[maxn * 2];
int be[maxn], l, n, low[maxn], dfn[maxn], m, k, b[maxn], br[maxn];
stack<int> s;
queue<int> q;
ll ans1, ans2;
void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}
void tarjan(int now)
{
  dfn[now] = low[now] = ++m;
  s.push(now);
  br[now] = 2;
  int t = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (!br[to])
    {
      ++t;
      tarjan(to);
      low[now] = min(low[now], low[to]);
    }
    else
    if (br[to] == 2)
      low[now] = min(low[now], dfn[to]);
    if (low[to] >= dfn[now]) b[now] = 1;
  }
  if (now == 1) b[now] = t == 1 ? 0 : 1;
  if (dfn[now] <= low[now])
    while (s.top() != now)
    {
      br[s.top()] = 1;
      s.pop();
    }
}
void bfs(int no)
{
  q.push(no);
  b[no] = -1;
  int tot = 1, g = 0;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (b[to] == -1 || b[to] == no + 10) continue;
      if (b[to])
      {
        ++g, b[to] = no + 10;
        continue;
      }
      b[to] = -1;
      ++tot;
      q.push(to);
    }
  }
  if (g == 1) ans2 = ans2 * tot, ++ans1;
}
int main()
{
  while (cin >> n && n)
  {
    ++k;
    memset(b, 0, sizeof(b));
    memset(be, 0, sizeof(be));
    memset(br, 0, sizeof(br));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    l = 0;
    m = 0;
    ans1 = 0;
    ans2 = 1;
    for (int i = 0; i < n; i++)
    {
      int fr, to;
      scanf(“%d%d”, &fr, &to);
      b[fr] = b[to] = 1;
      makeline(fr, to);
      makeline(to, fr);
    }
    ++n;
    int t = 0;
    for (int i = 1; i <= n; i++)
      if (b[i]) t++;
    memset(b, 0, sizeof(b));
    tarjan(1);
    for (int i = 1; i <= n; i++)
      if (!b[i]) bfs(i);
    if (!ans1) ans1 = 2, ans2 = t * (t – 1) / 2;
    printf(“Case %d: %lld %lld\n”, k, ans1, ans2);
  }

}

发表评论