tips:树是一种特殊的图 是无环连通图
有向图边有方向 如a->b
无向图边没有方向 a<->b
无向图是特殊的有向图 我们就先理解有向图的储存
1.邻接矩阵 其实就是一个二维数组 g[a][b]就存储a->b 有权重就是权重 没有就是bool值表示有无边 邻接矩阵不能有重边 只能保留一条 这个比较浪费空间
2.邻接表 就是n个节点 每个都开单链表 就跟哈希拉链法一样
每个h[i]链中表示的是连接i结点的所有结点 也就是为每一个点都开一个单链表 里面是无序的
所以h[i]存的是n个头结点
[存邻接表] [c++]1
2
3
4
5
6
7
8
9
10
11
12
| const int N=10010;
int h[N],ne[N],e[N],st[N],idx;
void add(int a,int b)
{
e[idx]=b; //存编号
ne[idx]=h[a]; //插入 让此结点的下一结点指向之前的头结点
h[a]=idx; //替换头结点
idx++;
}
|
[树的重心(dfs用法)] [c++]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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
const int N=1001000;
bool st[N]; //存有没有遍历过
int h[N],e[N],ne[N];
int n;
int ans=N;
int idx=0;
void add(int a, int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
int dfs(int u)
{
st[u]=true;
int sum=1; //当前子树大小为1 因为包含当前这个点
int res=0; //删掉点后每一个连通块的最大值
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j); //当前子树的子树大小
res=max(res,s); //子树的子树也是一部分
sum+=s; //这是归的一个过程 只能意会
}
}
res=max(res,n-sum); //放连通块中点的最大值
ans=min(res,ans);
return sum;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a); //无向图
}
dfs(1);
cout <<ans<<endl;
return 0;
}
|
[图的层次遍历] [c++]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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <cstring>
#include <iostream>
using namespace std;
const int N=1e5+10;
int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离 d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点
void add(int a, int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt=0;
q[0]=1; //0号节点是编号为1的节点
memset(d,-1,sizeof d);
d[1]=0; //存储每个节点离起点的距离
//当我们的队列不为空时
while(hh<=tt)
{
//取出队列头部节点
int t=q[hh++];
//遍历t节点的每一个邻边
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
//如果j没有被扩展过
if(d[j]==-1)
{
d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
q[++tt] = j; //把j结点 压入队列
}
}
}
return d[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
}
|
拓扑序列
对于一个图中所有点构成的序列A满足 对于图中每一条边(x,y) x在A中都出现在y之前
简而言之所有边都是从前指向后的 有向无环图(拓扑图)一定存在拓扑序列
入度:有多少条边指向自己
出度：有多少边指向别人
性质 一个有向无环图一定存在一个入度为0的点
所有入度为0的点(无任何点指向自己的点)可以作为起点
1.将所有入度为0的点入队
2.宽搜过程 枚举所有初边
[拓扑图] [c++]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
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,idx,e[N],ne[N],h[N],d[N],q[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool topp()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
{
if(!d[i]) q[++tt]=i; //入度为0的编号入队
}
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i]) //拓展队头元素
{
int j=e[i];
d[j]--; //删除边 也就是对应点入度-1
if(d[j]==0) q[++tt]=j;
}
}
return tt==n-1; //如果队尾下标已经n-1 说明插入了n个元素 排列完成
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
d[y]++;
}
if(topp())
{
for(int i=0;i<n;i++) cout<<q[i]<<" ";
cout<<endl;
}
else cout<<-1<<endl;
}
|
