517pj训练-2

图与树的存储与遍历

邻接表较为简单,就是插入一条边时它作为这个点下的第一条,记为head,另一个点用to储存,原来的第一条就直向它,用next储存

例题 T1

邻接表+DFS染色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,head[1000005],nex[2000005],to[2000005],cnt,vis[1000005],ans;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
void add(int a,int b)
{
nex[++cnt]=head[a],to[cnt]=b,head[a]=cnt;
nex[++cnt]=head[b],to[cnt]=a,head[b]=cnt;
}
void dfs(int root)
{
vis[root]=1;
for(int i=head[root];i!=-1;i=nex[i])
if(!vis[to[i]])dfs(to[i]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)head[i]=-1;
while(m--)
{
x=read(),y=read();
add(x,y);
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i);
ans++;
}
}
printf("%d\n",ans);
}