hdu 4582 DFS spanning tree

1348 단어
처음에는 가로 변 이 있 는 지 없 는 지 에 대해 고민 하 다가 데이터 구조의 표현 에 걸 렸 다.진심 요 리 는 볼 수 없 으 니 생각 부터 데이터 구조 까지 모두 다른 사람의 것 을 참고 할 수 밖 에 없다.
#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
const int MAXN = 2005;
vector<int> ee[MAXN], dd[MAXN];
bitset< MAXN > aa[MAXN];
int m, n, res;
int vis[MAXN];
void dfs(int u, int pre)
{
	vis[u] = 1;
	aa[u].reset();
	for (int i = 0; i< dd[u].size(); ++i)
	{
		int v = dd[u][i];
		if (vis[v])	aa[u][v] = 1;
	}
	for (int i = 0; i< ee[u].size(); ++i)
	{
		int v = ee[u][i];
		if (v!=pre)
		{
			dfs(v, u);
		}
	}
	if (pre == -1) return;
	else if (aa[u].test(pre)) ++res;
	else aa[pre] |= aa[u];
}
int main() 
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
	while (scanf("%d%d", &n, &m) != EOF && n+m)
	{
		for (int i = 1; i<=n; ++i) ee[i].clear(), dd[i].clear();
		memset(vis, 0, sizeof vis);
		res = 0;
		for (int i = 0; i< n-1; ++i)
		{
			int u,v;
			scanf("%d%d", &u, &v);
			ee[u].push_back(v); ee[v].push_back(u);
		}
		for (int i = n-1; i< m; ++i)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			dd[u].push_back(v); dd[v].push_back(u);
		}
		dfs(1,-1);
		printf("%d
", res); } return 0; }

좋은 웹페이지 즐겨찾기