题1：*阳光大学：洛谷1330
算法分析：
首先这个图，可能不连通，我们针对其中一个联通分量来看：如果我们在一个点放下了一只河蟹，那么那个点与之邻接的所有点都不可以再放河蟹。那么对于一个点，我们就有两个策略：放河蟹与不放河蟹。这也就对应了一个节点的两个状态：0（不放）或者1（放）。我们可以以这个联通分量的任意一个点作为深度搜索的起点，然后进行深度遍历，我们遍历的目的其实只是为了检测在图被 0/1点铺满的时候，会不会有任意一条边的两个点都是 0的情况，如果有这种情况，那么就是Impossible了！因为这样就有一条边未被*。
那如果可以被*，我们怎么计算最少需要放多少个河蟹呢？对于一个联通子图，我们需要统计放 1的点的个数和放 0的点的个数的最小值，因为放 1的点和 0的点其实状态可以互换，所有我们选择其中的最小值即可。
AC代码：
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e4 + 5;
vector<int> G[maxn];
int n, m, a, b, ans, vis[maxn], cnt[2], col[maxn];// col[] 数组存下每个点的状态，以便检查合法性
inline int Min(int x, int y) { return x < y ? x : y; }
bool dfs(int p, int c){
if(vis[p]){
if(c == col[p])
return true;
else
return false;
}// 新遍历的点已经被访问过了，最后一步合法说明这个联通分量合法
vis[p] = 1, col[p] = c, cnt[c]++;
for(int i = 0;i < (int)G[p].size();++i)
if(!dfs(G[p][i], c ^ 1))
return false;
return true;
}
int main(){
scanf("%d %d", &n, &m);
while(m--){
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1;i <= n;++i){
cnt[0] = cnt[1] = 0;
if(!vis[i]){
if(!dfs(i, 0)){
printf("Impossible");
return 0;
}
else
ans += Min(cnt[0], cnt[1]);
}
}
printf("%d", ans);
return 0;
}
题2：图的遍历：洛谷3916
算法分析：
这一题乍一看感觉这数据规模暴力搜DFS貌似过不去啊？？？
对 1-n 的每一个点求这个点能到达的编号最大的点，这个感觉会有很多无用的搜索啊。我们试着把样例画一下，发现过程如下：
1 -> 2 -> 4 ->3
于是输出： 4 4 3 4
那么我们不如反过来，反向建边，从大的编号节点开始深度遍历，因为与较大节点能够可达的节点的结果一定是这个较大节点，如果不能与较大节点可达，那么它的值一定就小于较大节点！
AC代码：
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> G[maxn];
int n, m, a, b, ans[maxn], vis[maxn];
void dfs(int p, int k){
if(vis[p]) return ;
vis[p] = 1;
ans[p] = k;
for(int i = 0;i < (int)G[p].size();++i)
if(!vis[G[p][i]])
dfs(G[p][i], k);
}
int main(){
scanf("%d %d", &n, &m);
while(m--){
scanf("%d %d", &a, &b);
G[b].push_back(a);// 反向建边
}
for(int i = n;i >= 1;--i)
if(!vis[i])
dfs(i, i); //新的联通链，最大的编号就是初始编号
for(int i = 1;i <= n;++i)
printf("%d ", ans[i]);
return 0;
}
题3：基础题：查找文献 洛谷5318
算法分析：
这就不分析了，跑一遍dfs和一遍bfs就完事了
AC代码：
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> G[maxn];
int n, m, a, b, vis[maxn];
void dfs(int p){
if(vis[p]) return ;
vis[p] = 1;
printf("%d ", p);
for(int i = 0;i < (int)G[p].size();++i)
if(!vis[G[p][i]])
dfs(G[p][i]);
}
void bfs(int p){
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(p);
vis[p] = 1;
while(!q.empty()){
int Now = q.front(); q.pop();
printf("%d ", Now);
for(int i = 0;i < (int)G[Now].size();++i)
if(!vis[G[Now][i]])
{
vis[G[Now][i]] = 1;
q.push(G[Now][i]);
}
}
}
int main(){
scanf("%d %d", &n, &m);
while(m--){
scanf("%d %d", &a, &b);
G[a].push_back(b);
}
for(int i = 1;i <= n;++i)
sort(G[i].begin(), G[i].end());
dfs(1);
printf("\n");
bfs(1);
return 0;
}
题4：无序字母对 洛谷1341
算法分析：
这题太坑了！！！
这题可以这样抽象建模：
单词：边（字符就是端点）
结果字符串：就是一个路径
需要寻找每个单词都出现的字符串：找到每条边都走到的路径（欧拉路径）
欧拉路径的算法分析：
欧拉路本质就是一个dfs，存在的条件是：
条件1：入度为奇数的点有0个或2个（0个是欧拉回路）
条件2：它一定要是一个联通图（联通性用并查集或者dfs）
注意事项：倒着存储点。
坑点分析：
1：自环用dfs不怕
2：老是RE（这个真的有点玄学……）
AC代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 3005;
int m, vis[maxn], deg[maxn], G[maxn][maxn], isOK, s, cnt, ans[maxn];
char a, b;
void dfs(int p){
if(vis[p]) return ;
vis[p] = 1;
for(int i = 0;i < maxn;++i)
if(!vis[i] && G[p][i])
dfs(i);
}
void euler(int p){
for(int i = 0;i < maxn;++i){
if(G[p][i]){
G[p][i]--;
G[i][p]--;
euler(i);
}
}
ans[cnt++] = p;
return ;
}
int main(){
cin >> m;
for(int i = 0;i < m;++i){
cin >> a >> b;
G[a - 'A'][b - 'A']++;
G[b - 'A'][a - 'A']++;
deg[a - 'A']++;
deg[b - 'A']++;
}
if(1 == m){
if(a > b)
cout << b << a;
else
cout << a << b;
return 0;
}
for(int i = 0;i < maxn;++i)
if(deg[i] & 1)
{
isOK++;
if(!s)
s = i;
}
if(0 != isOK && 2 != isOK){
dfs(s);
for(int i = 0;i < maxn;++i)
if(!vis[i] && deg[i])
{
isOK = 1;
break;
}
}
if(0 != isOK && 2 != isOK)
cout << "No Solution";
else{
euler(s);
for(int i = cnt - 1;i >= 0;--i)
cout << char(ans[i] + 65);
}
return 0;
}
// IcCvXggwPpl