传送门啦
这个题就是tarjan强连通分量与入度的例题了。
思路:
利用缩点的思想,先预处理一下所有的强连通分量,然后把每个强连通分量内的所有节点看做一个节点,然后处理一张新图,然后检查每个点的入度,然后取入度为 0 的点(缩点后)的个数,即为信息出发点。
可能有人想问为什么??
大体说明一下:
1.充分性证明:如果入度为 0 的点不是信息出发点,那么这个点必定不会接收到任何节点发出的信息,因为它的入度为 0 。
2.必要性证明:如果信息出发点不是入度为0的点,那么其必有入度点,使其覆盖点更多,而我们要找至少多少个点。
还是先明确一下各个数组的意思吧:
dfn[i]:i点的时间戳
low[i],表示这个点以及其子孙节点连的所有点中dfn最小的值
stack[],表示当前所有可能能构成是强连通分量的点。
ins[i],表示 i 是否在stack[ ]数组中
num[i],表示第 i 个强连通分量中有多少个点
belong[i],表示第 i 点在哪一个强连通分量里
in[i]:表示第 i 个强连通分量的入度是多少。
以下就是怎么处理入度:
for(int i=1;i<=m;i++){
if(belong[edge[i].from] != belong[edge[i].to])
in[belong[edge[i].to]]++;
}
解释一下:
枚举边,比较这条边起点和终点是否在同一个强连通分量中,如果不在,这条边终点的入度++
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 5e5 + 6;
int n,m,u,v;
int head[maxn],tot;
int dfn[maxn],low[maxn],ind;
int stack[maxn],top,belong[maxn],num[maxn],cnt;
int in[maxn];//表示某个点的入度
int ans;
bool ins[maxn];
struct Edge{
int from,to,next;
}edge[maxm];
void add(int u,int v){
edge[++tot].to = v;
edge[tot].from = u;
edge[tot].next = head[u];
head[u] = tot;
}
int read(){
char ch = getchar();
int f = 1 , x = 0;
while(ch > '9' || ch < '0'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void tarjan(int x){
dfn[x] = low[x] = ++ind;
stack[++top] = x;
ins[x] = true;
for(int i=head[x];i;i=edge[i].next){
int v = edge[i].to;
if(ins[v]) low[x] = min(low[x] , dfn[v]);
if(!dfn[v]){
tarjan(v);
low[x] = min(low[v] , low[x]);
}
}
int k;
if(dfn[x] == low[x]){
++cnt;
do{
k = stack[top];
num[cnt]++;
top--;
ins[k] = false;
belong[k] = cnt;
} while(k != x);
}
}
int main(){
n = read(); m = read();
for(int i=1;i<=m;i++){
u = read(); v = read();
add(u , v);
}
for(int i = 1;i <= n ;++i) belong[i] = i;
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;i++){
if(belong[edge[i].from] != belong[edge[i].to])
in[belong[edge[i].to]]++;
}
for(int i=1;i<=cnt;i++)
if(in[i] == 0)
ans++;
printf("%d\n",ans);
return 0;
}