七桥问题和一笔画

依然用vector 去构建图 , 这个已经会了应该去学一点别的了　　不错不错 ,

这次用vector 构图超时了 , 如果以后做题的话 , 看到可能会超时的题就应该先避开看看别的再说

先付上超时代码虽然超时了不过答案应该是正确的

 1 /*  认真体会  搜索不是一种形式 而是一种思想     */
 2 /*判断图 是否连同  我想的一个简单粗暴的办法就是  分别从每个点都走一次  看看有没有 那一次 能把所有的点都走一遍的*/
 3 #include<stdio.h>
 4 #include<vector>
 5 #include<string.h>
 6 using namespace std;
 7 vector<int>v[1005];
 8 int sum,visited[1005],q1,q;       //用于判断这个图 是否走过
 9 void DFS(int n)
10 {
11     if(q1==1)
12         return ;
13     for(int i=0;i<v[n].size();i++)
14     {
15         if(!visited[v[n][i]])
16         {
17             sum+=v[n][i];
18             visited[v[n][i]]=1;
19             DFS(v[n][i]);
20             if(sum==q)
21             {
22                 q1=1;
23                 return ;
24             }
25             visited[v[n][i]]=0;
26             sum-=v[n][i];
27         }
28     }
29 }
30 int main()
31 {
32     int n,m,i,j,t,a,b;
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d%d",&n,&m);
37         for(i=0;i<m;i++)
38         {
39             scanf("%d%d",&a,&b);
40             v[a].push_back(b);    //建立起来互相连通的 图
41             v[b].push_back(a);
42         }
43         q=(1+a)*a;   //  偶数和奇数相乘 一定是偶数
44         q/=2;
45         for(sum=n,q1=0,i=1;i<=n;i++)  //  分别从 每一个节点开始  搜索 看看图是否连同
46         {
47             memset(visited,0,sizeof(visited));
48             visited[n]=1; //这一点标记为  以访问
49             DFS(i);
50             if(q1==1)
51                 break;
52         }
53         if(q1==1)
54             printf("Yes
");
55         else
56             printf("No
");
57     }
58     return 0;
59 }

一笔画问题:　　一 : 只有偶点可以一笔画并且可以以任意一个点作为起点

　　　　　　　二 : 只有两个奇点可以一笔画出但是必须分别以这两个奇点为起点开始

　　　　　　　三 : 奇数点超过两个的时候不能一笔画

 1 /*  一直纠结到现在  然而 还是没有做出来  ,  显示的是 答案错误*/
 2 #include<stdio.h>
 3 #include<vector>
 4 #include<string.h>
 5 using namespace std;
 6 vector<int>v[1005];
 7 int n,m,mark[1005],visited[1005];
 8 void DFS(int i)
 9 {
10     for(int j=0;j<v[i].size();j++)
11     {
12         if(visited[v[i][j]])
13         {
14             visited[v[i][j]]=1;
15             mark[v[i][j]]=1;
16             DFS(v[i][j]);
17             visited[v[i][j]]=0;
18         }
19     }
20 }
21 int main()
22 {
23     int flag[1005],t;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d%d",&n,&m);
28         memset(v,0,sizeof(v));
29         memset(visited,0,sizeof(visited));
30         memset(mark,0,sizeof(mark));
31         memset(flag,0,sizeof(flag));
32         for(int i=0;i<m;i++)
33         {
34             int a,b;
35             scanf("%d%d",&a,&b);
36             v[a].push_back(b);
37             v[b].push_back(a);
38             flag[a]++;
39             flag[b]++;
40         }
41         int q=1,count=0;
42         for(int i=1;i<=n;i++)
43         {
44             if(mark[i]==0)   // 是否所有的  点 都走过
45                 q=0;             //  如果不能的话  标记 flag为  1
46             if(flag[i]%2!=0)   // 判断   有几个 奇数点
47                 count++;
48         }
49         if(flag&&(count==0||count==2))    //
50         {
51             printf("Yes
");
52         }
53         else
54         {
55             printf("No
");
56         }
57     }
58 }

就那一下下我要放弃了 , 然而挣扎了最后一次成功了两天的努力没有白费 , 以后写变量的时候一定考虑作用范围函数条理清晰不互相干扰

 1 /*不放弃 , 多学习 , 多借鉴 ,坚持自己的方法 , 不成为别人 , 不迷失自己*/
 2 #include<stdio.h>
 3 #include<vector>
 4 #include<string.h>
 5 using namespace std;
 6 vector<int>v[1005];
 7 int n,m,mark[1005],visited[1005];
 8 void DFS(int i)
 9 {
10     for(int j=0;j<v[i].size();j++)
11     {
12         if(!mark[v[i][j]])
13         {
14             mark[v[i][j]]=1;
15             DFS(v[i][j]);
16         }
17     }
18 }
19 int main()
20 {
21     int flag[1005],t;
22     scanf("%d",&t);
23     while(t--)
24     {
25         scanf("%d%d",&n,&m);
26         memset(v,0,sizeof(v));
27         memset(visited,0,sizeof(visited));
28         memset(mark,0,sizeof(mark));
29         memset(flag,0,sizeof(flag));
30         for(int i=0;i<m;i++)
31         {
32             int a,b;
33             scanf("%d%d",&a,&b);
34             v[a].push_back(b);
35             v[b].push_back(a);
36             flag[a]++;
37             flag[b]++;
38         }
39         DFS(1);
40         int q=1,count=0;
41         for(int i=1;i<=n;i++)
42         {
43             if(mark[i]==0)   // 是否所有的  点 都走过
44                 q=0;             //  如果不能的话  标记 flag为  1
45             if(flag[i]%2!=0)   // 判断   有几个 奇数点
46                 count++;
47         }
48         if(q&&(count==0||count==2))    //
49         {
50             printf("Yes
");
51         }
52         else
53         {
54             printf("No
");
55         }
56     }
57 }

下面开始用并查集做 (因为是第一次做　　先上我学习的干货 ) http://www.cnblogs.com/A-FM/p/5285188.html

 1 /*    已经做过了优化       */
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 int sum,father[1001],a[1001];
 6 int find(int x)                      //  做了时间上的优化 ,但是 在空间复杂度上比较高
 7 {
 8     if(x!=father[x])
 9         father[x]=find(father[x]);
10     sum++;
11     return father[x];
12 }
13 void merge(int x,int y)    // 做了时间复杂度上的优化  让并查集的 深度尽量  浅
14 {
15     int sum1,sum2;
16     sum=0;
17     x=find(x);
18     sum1=sum;        //    x  的深度
19     sum=0;
20     y=find(y);
21     sum2=sum;       //    y   的深度
22     if(x!=y)
23     {
24         if(sum1>sum2)
25             father[y]=x;
26         else
27             father[x]=y;
28     }
29 }
30 int main()
31 {
32     int N,P,Q,A,B;
33     int i,s,j;
34     while(~scanf("%d",&N))
35     while(N--){
36         s=j=0;
37         memset(a,0,sizeof(a));
38         scanf("%d %d",&P,&Q);
39         for(i=1;i<=P;i++)
40             father[i]=i;
41         while(Q--){
42             scanf("%d %d",&A,&B);
43             a[A]++;
44             a[B]++;
45             merge(A,B);
46         }
47         for(i=1;i<=P;i++){
48             if(father[i]==i)
49                 j++;
50             if(a[i]&1)
51                 s++;
52         }
53         if(j==1&&(s==0||s==2))
54             printf("Yes
");
55         else
56             printf("No
");
57     }
58     return 0;
59 }