Codeforces 第 254 轮（第 2 部分）

Note In the first sample, there's only one way to pour, and the danger won't increase. In the second sample, no matter we pour the 1 st chemical first, or pour the 2 nd chemical first, the answer is always 2 . In the third sample, there ar

Note

In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

写给自己:水水的题目, 竟然WA,一直找不到错误的地方. 最后才发现思路和细节都没有错,只是答案输出的类型精度不够(应该用long long 的只用了int).多么痛的领悟.出来献丑,不忘耻辱.

分析: 把各种化学物品的反应关系画成图, 可知只要用任一种遍历图(这个图可能是非连通的)的方法(DFS,BFS,并查集均可)遍历它便可求解(存在一条边则danger翻倍).

如下使用"邻接矩阵表示的DFS":

#include<stdio.h>
#include<string.h>
#define maxn 55
int G[maxn][maxn],vis[maxn];
int n;
long long ans;
void DFS(int v)
{
    int w;
    vis[v]=1;
    for(w=1;w<=n;w++)
        if(G[v][w]!=0 && vis[w]==0)
        {   ans=ans*2;  DFS(w); }
}
void DFSTraverse()
{
    int i;
    for(i=1;i<=n;i++)
        if(vis[i]==0)
        DFS(i);
}
int main()
{
	int m;
	int a,b;
	scanf("%d%d",&n,&m);
	memset(G,0,sizeof(G));
	memset(vis,0,sizeof(vis));
	ans=1;
	while(m--)
    {
        scanf("%d%d",&a,&b);
        G[a][b]=G[b][a]=1;
    }
    DFSTraverse();
    printf("%lld\n",ans);
	return 0;
}

另外, 借鉴别人并查集的做法: