[蓝桥杯 2013 国 C] 危险系数
题目链接：P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
割点：
删除这个顶点集合以所有顶点相关联的边以后，图的连通分量增多
其实就是求图的割点，找到“关键枢纽”，因为是稀疏图，所以用邻接表存图。
遍历起点->终点的所有路径（DFS），在遍历过程中，如果可以到达终点，则给中途经过的点的标记＋1，找到从起点到终点路径数目相同的点（除去起点和终点），该数目即为ans
1 #include <bits/stdc++.h>
2 #define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
3 using namespace std;
4 const int N=2010;
5 int n,m;
6 bool vis[N];
7 int st,ed;
8 int tot;//表示起点到终点的路径数
9 int cnt[N];
10 int ans;
11 int h[N],e[N],ne[N],idx;
12 void add(int a,int b)
13 {
14 e[idx]=b,ne[idx]=h[a],h[a]=idx++;
15 }
16 void dfs(int u)
17 {
18 vis[u]=true;
19 if(u==ed)
20 {
21 tot++;
22 for(int i=1;i<=n;i++)
23 {
24 if(vis[i])cnt[i]++;
25 }
26 return;
27 }
28 for(int i=h[u];i!=-1;i=ne[i])
29 {
30 int j=e[i];
31 if(!vis[j])
32 {
33 dfs(j);
34 vis[j]=0;
35 }
36 }
37 return;
38
39 }
40 int main()
41 {
42 io;
43 cin>>n>>m;
44 memset(h,-1,sizeof h);
45 for(int i=0;i<m;i++)
46 {
47 int a,b;
48 cin>>a>>b;
49 add(a,b),add(b,a);
50 }
51 cin>>st>>ed;
52 dfs(st);
53 for(int i=1;i<=n;i++)
54 {
55 if(cnt[i]==tot)ans++;
56 }
57 ans-=2;
58 cout<<ans;
59 return 0;
60 }
图的遍历
题目链接：P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
稀疏图邻接表存图，反向真妙我真傻，从大到小遍历，经过的直接赋值最大点，O(n)复杂度，要不然1e5(⊙﹏⊙)，基本正向就挂了
反向建图+DFS，不会缩点qwq
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10;
4 int e[N],ne[N],idx,h[N];
5 bool st[N];
6
7 int ans[N];//用来存储答案
8 void add(int a,int b)//表示在a后加入b这个点
9 {
10 e[idx]=b,ne[idx]=h[a],h[a]=idx++;
11 }
12 void dfs(int u,int a)//对u这个节点赋值a
13 {
14 ans[u]=a;
15 st[u]=true;
16 for(int i=h[u];i!=-1;i=ne[i])
17 {
18 int j=e[i];
19 if(!st[j])dfs(j,a);
20 }
21 }
22 int main()
23 {
24 memset(h,-1,sizeof h);
25 int n,m;
26 cin>>n>>m;
27 for(int i=0;i<m;i++)
28 {
29 int a,b;
30 cin>>a>>b;
31 add(b,a);//反向建图
32 }
33 for(int i=n;i>=1;i--)
34 {
35 if(!st[i])dfs(i,i);
36 }
37 for(int i=1;i<=n;i++)
38 cout<<ans[i]<<' ';
39 }
【福建省历届夏令营】阳光大学
题目链接：P1330 封锁阳光大学 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二分图，其实就是想把相邻的两个点染成不同的颜色，在每个连通块中加上两个颜色数目最小的点的数量，最后即为我要堵的答案
1 #include <bits/stdc++.h>
2 #define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
3 using namespace std;
4 const int N=1e5+10;
5 int n,m;
6 int h[N],e[N],ne[N],idx;
7 void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
8 int cnt[3];//表示1和2的二分子连通图各自的数量
9 int color[N];
10 bool dfs(int u,int c)//节点是u，c表示颜色
11 {
12 color[u]=c;
13 cnt[c]++;
14 for(int i=h[u];i!=-1;i=ne[i])
15 {
16 int j=e[i];
17 if(!color[j])//如果j这个点还没被染色
18 {
19 if(!dfs(j,3-c))return false;//如果接下来染色失败
20 }
21 else if(color[j]==c)return false;//如果染过色了，但是是冲突的
22 }
23 return true;
24 }
25 signed main()
26 {
27 io;
28 cin>>n>>m;
29 memset(h,-1,sizeof h);
30 while(m--){int a,b;cin>>a>>b;add(a,b);add(b,a);}
31 int ans=0;
32 for(int i=1;i<=n;i++)
33 {
34 cnt[1]=0,cnt[2]=0;
35 if(!color[i])
36 {
37 if(!dfs(i,1)){cout<<"Impossible";return 0;}//没有被染色并且染色后还矛盾了
38 }
39 ans+=min(cnt[1],cnt[2]);
40 }
41 cout<<ans;
42 return 0;
43 }
标签：dfs,idx,int,ne,ACM,st,BFS,add,DFS From： https://www.cnblogs.com/Zac-saodiseng/p/16927263.html