2378.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2378 on 2006-10-05 at 10:56:48 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 320000;

class Graph {
public:
	vector<int> g[N];
	int n, dfn[N], low[N], cur[N], cnt;
	int stack[N], top, ps[N], ptop;
public:
	int dfs(int, int);
	bool make();
};
int Graph::dfs(int src, int dis)
{
	int bn = 0;
	ptop = top = 0;
	stack[top++] = src; ps[ptop++] = -1;
	for(int i = 0; i < n; i++) cur[i] = g[i].size()-1;
	while(top != 0) {
		int	c = stack[top-1], cp = ps[ptop-1];
		if(dfn[c] == -1) { low[c] = dfn[c] = cnt++; }
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(no == cp) continue;
			if(dfn[no] == -1) { stack[top++] = no; ps[ptop++] = c; break; }
			if(dfn[no] < dfn[c]) low[c] <?= dfn[no];
			else low[c] <?= low[no];
			if(dfn[dis] == -1) continue;
			else if(low[no] > dfn[c] && dfn[no] <= dfn[dis]) bn++;
		}
		if(cur[c] < 0) { top--; ptop--; }
	}
	return bn;
}
bool Graph::make() {
	int m;
	scanf("%d %d", &n, &m);
	if(n == 0) return false;
	for(int i = 0; i < n; i++) g[i].clear();
	for(int i = 0; i < m; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(b); g[b].push_back(a);
	}
	int src, dis; scanf("%d %d", &src, &dis);
	memset(dfn, -1, sizeof(dfn)); cnt = 0;
	printf("%d\n", dfs(src, dis));
	return true;
}

Graph g;

int main()
{
	while(g.make());
	
	return 0;
}