1303 C Perfect Keyboard (DFS)

雨点打透心脏的1/2处 2021-07-16 14:32 256阅读 0赞

[题目][Link 1]

思路：这是一道图论题，通过观察我们可以发现如果一个字母旁边出现过三种及以上的其他字母则无解，并且出现环时也无解如：ABCA因为如果有一个环，那必然有两条边，而这个环想要跳到下一个字母必然还需要一条边.其实正确的答案就是链和一些孤立的点了。那么我们就可以把相邻的两个字母连线，统计度数，DFS遍历一遍度数<2的点，链从度为1开始及度为0的孤立点。最后再判断是否有点没被访问到，当出现环时（因为不dfs度为2的点）会出现有点没被访问，细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int tu[30][30];
    int visit[30];
    string ans = "";
    int Mod = 1e9 + 7;
    
    void dfs(int n)
    { 
    	if (visit[n])return;
    	visit[n]=1;
    	ans += char('a' + n - 1);
    	for (int i = 1;i <= 26;i++)
    	{ 
    		if (tu[n][i])dfs(i);
    	}
    }
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		string str;cin >> str;
    		ans = "";memset(tu, 0, sizeof(tu));memset(visit, 0, sizeof(visit));
    		map<int, int> ma;int f = 0;
    		for (int i = 0;i < str.size()-1;i++)
    		{ 
    			int a = str[i] - 'a' + 1, b = str[i + 1] - 'a' + 1;
    			tu[a][b] = 1;tu[b][a] = 1;
    		}
    		for (int i = 1;i <=26 ;i++)
    		{ 
    			for (int j = 1;j <= 26;j++)if (tu[i][j]) { ma[i]++;}
    		}
    		for (int i = 1;i <= 26;i++)if (ma[i] > 2)f = 1;
    		for (int i = 1;i <= 26;i++)if (ma[i] < 2)dfs(i);
    		if (ans.size() < 26 || f == 1)cout << "NO" << endl;
    		else cout << "YES" << endl << ans << endl;
    	}
    }

[Link 1]: https://codeforces.ml/contest/1303/problem/C