蓝桥杯七段码（并查集、DFS）

刺骨的言语ヽ痛彻心扉 2021-07-16 11:47 383阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]

## 思路 ##

先上并查集的，直接暴力枚举每一种状态，然后直接遍历全图，发现如果有两个相连的段都是亮着的，则将其归于一个集合，最后数总共有几个集合，如果超过了两个那必然会有不连续的情况。

Code

#include<iostream>
    
    using namespace std;
    
    const int Max=1e3+5;
    
    int f[Max];
    
    void init()
    { 
    	for(int i=1;i<=10;i++)f[i]=i;
    }
    int find(int x)
    { 
    	if(f[x]==x)return x;
    	else return f[x]=find(f[x]);
    }
    
    void merge(int a,int b)
    { 
    	if(find(a)!=find(b)) f[find(b)]=find(a);
    }
    
    int tu[100][100];
    
    int a[100];
    int ans=0;
    
    void dfs(int n)
    { 
    	if(n==8)
    	{ 
    		init();
    		for(int i=1;i<=7;i++)
    		{ 
    			for(int j=1;j<=7;j++)
    			{ 
    				if(a[j]&&a[i]&&tu[i][j])merge(i,j);
    			}
    		}
    		int sum=0;
    		for(int i=1;i<=7;i++)
    		{ 
    			if(a[i]&&find(i)==i)sum++;
    		}
    		if(sum==1) ans++;
    		return;
    	}
    	a[n]=1;
    	dfs(n+1);
    	a[n]=0;
    	dfs(n+1); 
    }
    
    int main()
    { 
    	tu[1][2]=tu[1][6]=1;
    	tu[2][1]=tu[2][7]=tu[2][3]=1;
    	tu[3][2]=tu[3][7]=tu[3][4]=1;
    	tu[4][3]=tu[4][5]=1;
    	tu[5][4]=tu[5][6]=tu[5][7]=1;
    	tu[6][5]=tu[6][1]=tu[6][7]=1;
    	tu[7][2]=tu[7][6]=tu[7][5]=tu[7][3]=1;
    	dfs(1);
    	cout<<ans;
    }

一开始我是想直接dfs的，但挂掉了。。就看看别人的题解，也用并查集过了。我说下我原本的方法，直接暴力dfs把能连接的全走一遍，如果发现对于一种状态只需要从一个点能走完所有亮着的点，则符合状态，但答案为600，感觉没啥地方不对劲，有老哥帮忙看一手吗。

Code

#include<iostream>
    #include<vector>
    using namespace std;
    
    int i[10];
    
    vector<int> vec[100];
    int b[100];
    
    void dfs(vector<int> lst )
    { 
    	for (int j = 0;j < lst.size();j++)
    	{ 
    		int v = lst[j];
    		if (b[v] == 0 && i[v] == 1)
    		{ 
    			b[v] = 1;
    			dfs(vec[v]);;
    		}
    	}
    }
    
    int main()
    { 
    	vec[1].push_back(2);
    	vec[1].push_back(6);
    	vec[2].push_back(1);
    	vec[2].push_back(7);
    	vec[2].push_back(3);
    	vec[3].push_back(2);
    	vec[3].push_back(7);
    	vec[3].push_back(4);
    	vec[4].push_back(3);
    	vec[4].push_back(5);
    	vec[5].push_back(4);
    	vec[5].push_back(6);
    	vec[5].push_back(7);
    	vec[6].push_back(5);
    	vec[6].push_back(1);
    	vec[6].push_back(7);
    	vec[7].push_back(2);
    	vec[7].push_back(6);
    	vec[7].push_back(3);
    	vec[7].push_back(5);
    	int ans = 0;
    
    	for(i[1]=0;i[1]<=1;i[1]++)
    		for (i[2] = 0;i[2] <= 1;i[2]++)
    			for (i[3] = 0;i[3] <= 1;i[3]++)
    				for (i[4] = 0;i[4] <= 1;i[4]++)
    					for (i[5] = 0;i[5] <= 1;i[5]++)
    						for (i[6] = 0;i[6] <= 1;i[6]++)
    							for (i[7] = 0;i[7] <= 1;i[7]++)
    							{ 
    								int sum = 0;
    								memset(b, 0, sizeof(b));
    								for (int j = 1;j <= 7;j++)
    								{ 
    									if (b[j] == 0&&i[j]==1)
    									{ 
    										dfs(vec[j]);
    										b[j] = 1;
    										sum++;
    									}
    									if (sum == 1)ans++;
    								}
    							}
    	cout << ans;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/47fdb790bee5405b9e09305e2393495f.png