Stock Chase hdu3357 图论-CSDN博客

本文提供 HDU 3357 的详细解题思路，介绍如何通过图论和有向图的环检测算法来解决该题目。讨论了在给定的有向图中，按照特定顺序添加边时避免形成环的方法，并实现了相应的更新操作。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

http://acm.hdu.edu.cn/showproblem.php?pid=3357

我把前辈的说明复制来。。 =.=

按所给的顺序，给出一条有向边，如果加上这条边会出现环，那就舍弃这条边，问一共有几条边要舍弃
如果加入的边a到b不会出现环，要做一次更新，有三类更新：
i->a->b->j => i->j;
i->a->b => i->b;
a->b->j => a->j

#include <iostream>
using namespace std;
#define N 250
bool relation[N][N];

int main(){
#ifndef ONLINE_JUDGE
	freopen("3357in.txt","r",stdin);
#endif
	int n,t,a,b,i,j,ans,ce=0;
	while (scanf("%d%d",&n,&t)!=EOF){
		if (!n&&!t)
			break;
		ce++;
		memset(relation,false,sizeof(relation));
		ans=0;
		while (t--){
			scanf("%d%d",&a,&b);
			if (relation[b][a]||a==b){  //如果出现环，或者自身成环，就舍弃
				ans++;
				continue;
			}
			if (relation[a][b])
				continue;
			relation[a][b]=true;
			for (i=1;i<=n;i++)   //i->a->b->j  == i->j
				if (relation[i][a])
					for (j=1;j<=n;j++)
						if (relation[b][j])
							relation[i][j]=true;
			for (i=1;i<=n;i++){
				if (relation[i][a])  //i->a->b == i->b
					relation[i][b]=true;
				if (relation[b][i])  //a->b->j == a->j
					relation[a][i]=true;
			}
		}
		printf("%d. %d\n",ce,ans);
	}
	return 0;
}