POJ 2942.Knights of the Round Table(デュアルコネクション)

簡単な問題解:
どの点が1つの図の奇環の二重連通成分内にあるかを判断することを意味する.
tarjanはすべての点二連通成分を求め,各二連通成分が奇環を形成しているか否かを二分図染色で判断し,どの点が内奇環内に現れるかを記録する
出力が奇環内にない点の数
code
 

/*

                  tarjan  

         ：

       1.                ，            dfn[n]

       2.      v low[v]                    .

            ,     v        u low[u]        low[v]         :

          1)dfn[v];

          2)dfn[w],     (v,w)

          3)low[u],  v     u

       3.          ,  :

         a)v   , v   1   

         b)v    ,      (v,u) ,  dfn[v]<=low[u].

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#define INF 1009

using namespace std;

int n, m, x, y;

bool g[INF][INF];

int low[INF], dfn[INF], sta[INF], ans[INF][INF], f[INF], ok[INF], Top, Max , tcc, t;

bool make (int x, int cow) {

	for (int i = 0; i < cow; i++) {

		int v = ans[tcc][i];

		if (x != v && g[x][v]) {

			if (f[v] == -1) {

				f[v] = !f[x];

				if (make (v, cow) ) return 1;

			}

			else if (f[v] == f[x]) return 1;

		}

	}

	return 0;

}

void check (int cow) {

	memset (f, -1, sizeof f);

	f[ans[tcc][0]] = 0;

	if (make (ans[tcc][0], cow) )

		for (int i = 0; i < cow; i++)

			ok[ans[tcc][i]] = 1;

}

void dfs (int k, int from) {

	sta[++Top] = k;

	low[k] = dfn[k] = ++t;

	for (int i = 1; i <= n; i++) {

		if (i == from || g[k][i] == 0 || k == i) continue;

		if (!dfn[i]) {

			dfs (i, k);

			low[k] = min (low[k], low[i]);

			if (dfn[k] <= low[i]) {

				ans[tcc][0] = k;

				int cow = 1;

				do

					ans[tcc][cow++] = sta[Top];

				while (sta[Top--] != i);

				if (cow > 2) check (cow), ++tcc;

			}

		}

		else low[k] = min (low[k], dfn[i]);

	}

	return ;

}

void Tarjan (int n) {

	memset (low, 0, sizeof low);

	memset (dfn, 0, sizeof dfn);

	Top = tcc = t = 0;

	for (int i = 1; i <= n; i++)

		if (dfn[i] == 0) dfs (i, -1);

}

int main() {

	while (~scanf ("%d %d", &n, &m) ) {

		if (n == 0 && m == 0) return 0;

		memset (g, 1, sizeof g);

		memset (ok, 0, sizeof ok);

		Max = 0;

		for (int i = 1; i <= m; i++) {

			scanf ("%d %d", &x, &y);

			g[x][y] = g[y][x] = 0;

		}

		Tarjan (n);

		int ans = 0;

		for (int i = 1; i <= n; i++)

			if (!ok[i]) ans++;

		printf ("%d
", ans);

	}

	return 0;

}