深搜，图论习题

最近做了几道相关题目，在这里分享一下：

1.

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
    
5.  
    
6.  
   int mm[1005][1005]; //记录是否有联系
7.  
   int vis[1005];
8.  
   int n,m,cnt=0;
9.  
   int count[1005];
10.  
    int ans=0;
11.  
    int strat,e; //注意要写到全局变量里，被调用函数要用
12.  
    void dfs(int u){
13.  
    vis[u]=1;//标记
14.  
    if(u==e){
15.  
    ans ;//一共有多少条
16.  
    for(int i=1;i<=n;i ){
17.  
    //记录此条路径下，经过哪些点
18.  
    if(vis[i])count[i] ;//是否为关键点
19.  
    }
20.  
    return;
21.  
    }
22.  
    for(int i=1;i<=n;i ){
23.  
    if(mm[u][i]&&!vis[i])//如果相连并且没有访问
24.  
    {
25.  
    dfs(i);
26.  
    vis[i]=0;//回溯，写在循环体里面
27.  
    }
28.  
    }
29.  
     
30.  
    }
31.  
    int main(){
32.  
    cin>>n>>m;
33.  
    int a,b;
34.  
    //初始化
35.  
    memset(mm,0,sizeof(mm));
36.  
    memset(vis,0,sizeof(vis));
37.  
    memset(count,0,sizeof(count));
38.  
    while(m--){
39.  
    cin>>a>>b;
40.  
    mm[a][b]=mm[b][a]=1;
41.  
    }
42.  
    //起点，终点
43.  
    cin>>strat>>e;
44.  
    dfs(strat);
45.  
    for(int i=1;i<=n;i ){
46.  
    if(count[i]==ans)//寻找与路径条数相同的点
47.  
    cnt ;
48.  
    }
49.  
    if(ans==0)cout<<-1<<endl;
50.  
    cout<<cnt-2<<endl;
51.  
    }

2.

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N=100005;
4.  
   vector<int>vec[100005];
5.  
   int n,m,a,b,k[100005];
6.  
   void dfs(int n,int m){
7.  
   if(k[n]) return;
8.  
   k[n]=m;
9.  
   for(int i=0;i<vec[n].size(); i){
10.  
    dfs(vec[n][i],m);
11.  
    }
12.  
    }
13.  
    int main(){
14.  
    cin>>n>>m;
15.  
    while(m--){
16.  
    cin>>a>>b;
17.  
    vec[b].push_back(a);
18.  
    }
19.  
    for(int i=n;i;--i){
20.  
    dfs(i,i);
21.  
    }
22.  
    for(int i=1;i<=n; i){
23.  
    cout<<k[i]<<" ";
24.  
    }
25.  
    }

3.

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   inline int read() //快速读取
4.  
   {
5.  
   int x = 0, f = 1;
6.  
   char ch = getchar();
7.  
   while (ch < '0' || ch > '9')
8.  
   {
9.  
   if (ch == '-')
10.  
    f = -1;
11.  
    ch = getchar();
12.  
    }
13.  
    while (ch >= '0' && ch <= '9')
14.  
    {
15.  
    x = (x << 1) (x << 3) (ch ^ 48);
16.  
    ch = getchar();
17.  
    }
18.  
    return x * f;
19.  
    }
20.  
    int m, n;
21.  
    const int N = 100005;
22.  
    int a[N];
23.  
    int t[2]; //记录颜色
24.  
    bool vis[N];
25.  
    vector<int> G[N];
26.  
    bool dfs(int u, int color)
27.  
    {
28.  
    vis[u] = true; //标记当前点已经访问过
29.  
    a[u] = color; //涂色
30.  
    t[color] ; //该种颜色的数量加一
31.  
    for (int i = 0; i < G[u].size(); i ) //遍历当前点的下一步能到达的所有点
32.  
    {
33.  
    int v = G[u][i]; //记录下一个点
34.  
    if (vis[v] && a[v] == a[u]) //下一个点访问过而且颜色跟当前颜色相同
35.  
    return 0; //就结束搜索，返回false
36.  
    else if (vis[v]==0) //没访问过
37.  
    {
38.  
    bool flag = dfs(v, (color 1) & 1); //将下一个点涂成不同颜色
39.  
    if (flag==0) //涂色不成功
40.  
    return 0;;; //就结束搜索，返回false
41.  
    }
42.  
    }
43.  
     
44.  
    return 1;
45.  
    }
46.  
    int main()
47.  
    {
48.  
    n = read();;;;
49.  
    m = read();
50.  
    for (int i = 1; i <= m; i )
51.  
    {
52.  
    int x = read(), y = read();
53.  
    G[x].push_back(y); ;;//无向图
54.  
    G[y].push_back(x);
55.  
    }
56.  
    int ans = 0;
57.  
    for (int i = 1; i <= n; i)
58.  
    if (!vis[i]) //如果该点没被标记
59.  
    {
60.  
     
61.  
    t[0] = t[1] = 0; //先将颜色数归零
62.  
    bool flag = dfs(i, 0);
63.  
     
64.  
    if (flag==0)
65.  
    {
66.  
    cout << "Impossible";
67.  
    return 0;
68.  
    }
69.  
    ans=ans min(t[0], t[1]);;; //答案加上颜色数小的那个
70.  
    }
71.  
    cout << ans;
72.  
    }

写这种题，一定要注意终止与判断条件。 

这篇好文章是转载于：学新通技术网