强连通，奇怪的缩点学习笔记？

缩点，难难难，不想学呜呜呜。板子：P3387 【模板】缩点
还好吧正常点，考虑对于一个有向图，进行缩点。呜呜呜我是废物。说几个我学的时候想了一段时间的问题：
（dfn[u]表示顶点u第几个被（首次）访问，low[u]表示顶点u及其子树中的点吗，其实就是用dfsx的方式记录嘛）
1.记录low的时候为什么要用最小值？因为它要找到最上面的那个点，防止环套环
2.在一个点已经入队之后应该给其打上标记，之后直接取min，在代码中有解释
3.重新建边的时候，去重，具体就是若是这条边已经建过了就算了，若是这建的边在一个环里也算了
4.记住啦，v的标记是一定要打的，dfsx的标记判断是其是否被走过，v的标记是判断虽然这个点之前走过了，但是它若是已经成环了的话就没必要再走一遍，应该直接取值。这个的话说不好，感性想想？
再说几个细节 ：
1.数组清空
2.环中的每个点的值都要放到成环的值中
3.注意栈的大小

#include
using namespace std;
int n,m,len=0,last[400001],tot=0,dfs_x=0,point=0,id[400001],a[400001];
int dfsx[400001],low[400001],q[400001],sum[400001],f[400001],ans=0;
bool v[400001];
struct pp
{
	int x,y,next;
};pp p[400001],L[400001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void tra(int now)
{
	low[now]=dfsx[now]=++dfs_x;
	q[++tot]=now;v[now]=true;
	for(int i=last[now];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) tra(y),low[now]=min(low[now],low[y]);
		else if(v[y]) low[now]=min(low[now],dfsx[y]);//如果这个点之前已经如果队了
		//那么明显的，dfsx应该比low小，不信自己画图看看...也不能这样说
		//只能说是，就是怎么说呢，就是能不回到最上面的那个点的嘛，所以要记录那个点的dfsx 
	}
	if(dfsx[now]==low[now])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[now]) 
		{ 
			id[q[tot]]=point;sum[point]+=a[q[tot]];
			v[q[tot]]=false;tot--;dfs_x--;
		}
	} 
	return ;
}
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y; 
}
void remake()
{
	memset(last,-1,sizeof(last));memset(p,0,sizeof(p));len=0;
	for(int i=1;i<=m;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(L[i].x==L[i].y||(L[i].x==L[i-1].x&&L[i].y==L[i-1].y)) continue ;
		ins(L[i].x,L[i].y);
	}
	return ; 
}
void dfs(int x,int fa)
{ 
	if(f[x]) return ;//为什么加这句？因为可能会有1->3,2->3,3->x... 这样的情况，那么三这个点会被走很多次，但是只应该走1次 
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;
		dfs(y,x);f[x]=max(f[x],f[y]);
	} 
	f[x]+=sum[x];
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));
	memset(v,false,sizeof(v));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) 
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);L[i].x=x,L[i].y=y;
	}
	memset(dfsx,0,sizeof(dfsx));
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) tra(i);
	}
	remake();memset(f,0,sizeof(f));
	for(int i=1;i<=point;i++)
	{ 
		if(!f[i]) dfs(i,i),ans=max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

现在学一个新的，先放别人的博客：https://www.cnblogs.com/collectionne/p/6847240.html，割点！！！P3388 【模板】割点（割顶），定义是：在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点。区区割点而已！不过如此，看我驱夺之势，如狼噬骨。不多说，思想的话也是类似于上面的，只不过，这个算法的想法是若是自己儿子的low没有小于自己的，那么明显的就不会成环，也不能这样说，只能说不会到这个节点的上面的点去，所以就可以判断了。其次是对于根节点你需要特判一下，就如果你有两个儿子就行（环不行）那么就好了。

//其实这个算法的具体思路就是，判断一个点的每一个儿子会不会往上面成环
//要是成了的话它low[y]肯定是小于dfsx[now]对吧 
#include
using namespace std;
int n,m,low[200001],dfsx[200001],len=0,last[200001],dfs_x=0;
int ans[200001],tot=0;
struct pp
{
	int x,y,next;
};pp p[500001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int now,int dd)
{
	int ch=0;dfsx[now]=low[now]=++dfs_x;
	for(int i=last[now];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y])
		{
			CNT(y,dd);low[now]=min(low[now],low[y]);//考虑从最上面的点过来	 
			if(low[y]>=dfsx[now]&&dd!=now) ans[now]=1;//如果有一个点能被断掉 
			if(dd==now) ch++;//根的情况 
		}
		low[now]=min(low[now],dfsx[y]);//取一手最小值 
	}
	if(ch>=2) ans[now]=1;//如果是根的话 
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(ans,0,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x); 
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) CNT(i,i);
	}
	for(int i=1;i<=n;i++)
	{
		if(ans[i]) tot++;
	}
	printf("%d\n",tot);
	for(int i=1;i<=n;i++)
	{
		if(ans[i]) printf("%d ",i);
	}
	return 0;
}
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

有一个差不多的边双定义看这个！（无向图双连通分量BCC（全网最好理解）网址太长了）注意一个小细节，反向边是不能用的，为什么？因为这是割边而不是点，可以搞懂概念再看看。P8436 【模板】边双连通分量

#include
using namespace std;
int n,m,len=1,last[5000001],low[5000001],dfsx[5000001],dfs_x=0;
int ans[5000001],point=0; 
bool v[5000001];
struct pp
{
	int x,y,next;
};pp p[5200001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int x,int fa)
{
	dfsx[x]=low[x]=++dfs_x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;//(v[i]) continue ;v[i]=v[i^1]=true;
		if(!dfsx[y])
		{
			CNT(y,i);low[x]=min(low[x],low[y]);
			if(dfsx[x]<low[y]) v[i]=v[i^1]=true;
		}
		else if(fa!=(i^1)) low[x]=min(low[x],dfsx[y]);
	}
	return ;	
} 
vector<int > t[5000001];
void dfs(int x)
{
	ans[x]=point;
	if(x) t[point].push_back(x);
	for(int i=last[x];i!=-1;i=p[i].next)
	{	
		int y=p[i].y;if(v[i]||ans[y]) continue ;
		dfs(y);	
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(v,false,sizeof(v));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) CNT(i,0);
	}
	for(int i=1;i<=n;i++)
	{
		if(!ans[i]) point++,dfs(i);
	}
	printf("%d\n",point);
	for(int i=1;i<=point;i++)
	{
		printf("%d ",t[i].size());
		for(int j=0;j<t[i].size();j++) printf("%d ",t[i][j]);
		printf("\n");
	} 
	return 0;
}
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
64
65
66
67
68

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G一道神奇的题目捏，题目的目的在于看出对环的处理。那么看出来是缩点之后，我不会了啊，一看题解，发现是若缩完的点之间，有一个点出度是0，那么可以发现有解，若是两个及以上，那么就无解。

#include 
using namespace std;
int n,m,len=0,last[500001],dfsx[500001],low[500001],dfs_x=0,q[500001],tot=0,point=0;
int ans[10001],siz[100001],in[100001],id[100001];
bool v[500001];
struct pp
{
	int x,y,next;
};pp p[500001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void Sh(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	q[++tot]=x;v[x]=true;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) Sh(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			id[q[tot]]=point;v[q[tot]]=false;
			siz[point]++;tot--,dfs_x--;
		}
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) Sh(i);
	}
	for(int x=1;x<=n;x++)
	{
		for(int i=last[x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;if(id[x]==id[y]) continue ;
			in[id[x]]++;
		}
	}
	int pd=0;
	for(int i=1;i<=point;i++)
	{
		if(!in[i])
		{
			if(pd) 
			{
				printf("0");
				return 0; 
			}
			else pd=i;
		}
	}
	printf("%d",siz[pd]);
	return 0;
}
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
64
65
66
67
68
69
70
71
72
73

P2863 [USACO06JAN]The Cow Prom S这个是一个新的板子，不过其实就是上面的简化版。就是环的个数（除了一个点）

#include
using namespace std;
int n,m,len=0,last[400001],dfsx[400001],low[400001],dfs_x=0;
int ans=0,q[400001],tot=0,siz[400001],point=0;
bool v[400001];
struct pp
{
	int x,y,next;
};pp p[4000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now; 
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			siz[point]++;v[q[tot--]]=false;
		} 
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(dfsx,0,sizeof(dfsx));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i); 
	}
	for(int i=1;i<=point;i++)
	{
		if(siz[i]>1) ans++;
	}
	printf("%d",ans);
	return 0;
}
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

我学缩点都是为了P4742 [Wind Festival]Running In The Sky，好吧之前拓扑的题哦，看出来就是拓扑+缩点啦。但挺麻烦的，记录两个值然后建图然后拓扑然后起飞芜湖。

#include
using namespace std;
int n,m,len=0,last[500001],dfsx[500001],low[500001],q[500001],to[500001],id[500001],tot=0,point=0;
bool v[500001];
int a[500001],f[500001],maxx[500001],dfs_x=0,in[500001];
struct node 
{
	int sum,maxx;
};node e[500001];
struct pp
{
	int x,y,next;
};pp p[1000001],L[1000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			e[point].sum+=a[q[tot]];e[point].maxx=max(e[point].maxx,a[q[tot]]);
			id[q[tot]]=point;v[q[tot]]=false;tot--;dfs_x--;
		}
	}
	return ;
}
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y;
}
void remake()
{
	memset(last,-1,sizeof(last));len=0;//mesmet(p,0,sizeof(p));
	for(int i=1;i<=m;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(L[i].x==L[i].y||(L[i].x==L[i-1].x&&L[i].y==L[i-1].y)) continue ;
		ins(L[i].x,L[i].y);in[L[i].y]++;
	}
	return ;
}
void gettop()
{
	memset(f,0,sizeof(f));memset(maxx,0,sizeof(maxx));
	int st=1,ed=1;
	for(int i=1;i<=point;i++)
	{
		f[i]=e[i].sum,maxx[i]=max(e[i].maxx,maxx[i]);
		if(!in[i]) to[ed++]=i;
	}
	while(st!=ed)
	{
		int x=to[st++];
		for(int i=last[x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;in[y]--;
			if(!in[y]) to[ed++]=y;
			if(f[y]<f[x]+e[y].sum)
			{
				f[y]=f[x]+e[y].sum;
				maxx[y]=max(e[y].maxx,maxx[x]);
			}
			else if(f[y]==f[x]+e[y].sum) maxx[y]=max(maxx[y],maxx[x]);
		}	
	}
	return ;
} 
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);L[i].x=x,L[i].y=y;
	}
	memset(v,false,sizeof(v));
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i);
	}
	remake();gettop();int ans1=0,ans2=0;
	for(int i=1;i<=point;i++) 
	{	
		if(ans1<f[i]||(ans1==f[i]&&ans2<maxx[i])) ans1=f[i],ans2=maxx[i];
	}
	printf("%d %d",ans1,ans2);
	return 0;
} 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

P1726 上白泽慧音呃看起来一道裸的缩点？错了！还是有一些结论的，就是越早的点会越早。用于求字典序。

#include
using namespace std;
int n,m,len=0,last[400001],dfsx[400001],low[400001],dfs_x=0,id[400001],point=0;
int q[400001],tot=0,siz[400001];
bool v[400001];
struct pp
{
	int x,y,next;
};pp p[800001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	
	if(dfsx[x]==low[x]) 
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			id[q[tot]]=point;siz[point]++;
			v[q[tot]]=false;tot--;dfs_x--;	
		}	
	} 
	return ;	
}
int ans[400001],maxsiz=0;
int main()
{
	memset(last,-1,sizeof(last));memset(dfsx,0,sizeof(dfsx));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,op;scanf("%d%d%d",&x,&y,&op);
		if(op==1) ins(x,y);
		else ins(x,y),ins(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i);
	}
	for(int i=1;i<=point;i++)
	{
		if(maxsiz<siz[i]) 
		{
			tot=0;
			maxsiz=siz[i];
			for(int j=1;j<=n;j++)
			{
				if(id[j]==i) ans[++tot]=j;
			}
		}
	}
	printf("%d\n",maxsiz);
	for(int i=1;i<=maxsiz;i++) printf("%d ",ans[i]);
	return 0;
}
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
64
65
66
67
68

P2746 [USACO5.3]校园网Network of Schools不知道是什么动静，题面都看不懂了。一番细思之下发现，第一问球的是求缩点后入度为0的个数，第二问求的是对于一个有向无环图（DAG）最少加几条边变成一个强连通（SCC），那么考虑第二问（第一问直接搞）我是想到了的，不过懒得写。

不妨想起一个结论（草sb提高组的）对于一个图若是每个点入度为1那么一定是一个联通图。好像是吧大概，然后发现对于每一个点只要发现出度入度都不为0那么就可以满足，所以取max（sumin，sumout）。

//你看起来心情不太好？
//有点
//你不应的
//讨论这个毫无意义
//都说了你早应该改一下的 
//算了吧
//蠢货
//那还能怎么办
//你说呢
//都说了
//闭嘴
#include
using namespace std;
int n,m,len=0,last[100001],dfsx[100001],low[100001],dfs_x=0,id[100001],in[100001],out[10001];
int q[100001],tot=0,point;
bool v[100001];
struct pp
{
	int x,y,next;
};pp p[100001],L[100001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			id[q[tot]]=point;v[q[tot]]=false;
			dfs_x--,tot--;
		}
	}
	return ;	
} 
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y;
}
void remake()
{
	for(int i=1;i<=len;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	sort(L+1,L+len+1,cmp);
	for(int i=1;i<=len;i++)
	{
		if(L[i].x==L[i].y||(L[i].x==L[i-1].x&&L[i].y==L[i-1].y)) continue ;
		in[L[i].y]++,out[L[i].x]++;//printf("*");
	}
} 
int main()
{
	memset(last,-1,sizeof(last));memset(dfsx,0,sizeof(dfsx));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{	
		int x;while(scanf("%d",&x))
		{
			if(x==0) break ;
			ins(i,x);L[len].x=i,L[len].y=x;//printf("**%d ",len);
		}
	}
	memset(v,false,sizeof(v));
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i);
	}
	remake();
	int ans1=0,ans2=0,sumin=0,sumout=0;
	for(int i=1;i<=point;i++) 
	{
		if(in[i]==0) sumin++,ans1++;
		if(out[i]==0) sumout++;
	}
	ans2=max(sumin,sumout);//printf("%d %d %d\n",sumin,sumout,point);
	if(point==1) printf("1\n0");
	else printf("%d\n%d",ans1,ans2);
	return 0;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

P1262 间谍网络过了，有点麻烦而已。

#include
#define int long long 
using namespace std;
int n,m,mm,len=0,last[100001],dfsx[100001],low[100001],dfs_x=0,id[100001];
int q[100001],tot=0,money[100001],sum[100001],in[100001],point=0;
bool v[100001];
struct pp
{
	int x,y,next;
};pp p[100001],L[100001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{//printf("%d ",x);
			sum[point]=min(sum[point],money[q[tot]]);
			v[q[tot]]=false;id[q[tot]]=point;
			tot--,dfs_x--;
		}
	}
	return ;
}
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y; 
} 
void remake()
{
	for(int i=1;i<=m;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(L[i].x==L[i].y||(L[i].x==L[i-1].x&&L[i-1].y==L[i].y)) continue ;
		in[L[i].y]++;
	}
	return ;
}
 main()
{
	memset(last,-1,sizeof(last));memset(money,63,sizeof(money));memset(sum,63,sizeof(sum));
	scanf("%lld%lld",&n,&mm);
	for(int i=1;i<=mm;i++) 
	{
		int x,k;scanf("%lld%lld",&x,&k);
		money[x]=k;
	}
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		ins(x,y);L[i].x=x,L[i].y=y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]&&money[i]!=money[0]) SH(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) 
		{	
			printf("NO\n%lld",i);
			return 0;
		}
	}
	remake();int ans=0;
	for(int i=1;i<=point;i++)
	{
		if(!in[i]) ans+=sum[i];
	}
	printf("YES\n%lld",ans);
	return 0;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

Checkposts随便水了一题：

#include
#define int long long 
using namespace std;
int n,m,len=0,last[520001],dfsx[520001],low[520001],dfs_x=0,id[520001];
int minn[520001],siz[520001],q[520001],tot=0,point=0,a[520001];
bool v[520001];int mod=1e9+7;
struct pp
{
	int x,y,next;
};pp p[520001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true,q[++tot]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],low[y]);
	}
	if(dfsx[x]==low[x]) 
	{
		point++;
		while(dfsx[q[tot]]>=dfsx[x])
		{
			int y=q[tot--];id[y]=point;dfs_x--,v[y]=false;
			if(minn[point]>a[y]) minn[point]=a[y],siz[point]=1;
			else if(minn[point]==a[y]) siz[point]++;
			siz[point]%mod;
		} 
	}
	return ;
}
signed main() 
{
	memset(last,-1,sizeof(last));
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),minn[i]=mod*52,siz[i]=0;
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		ins(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i);
	}
	int ans1,ans2=1;
	for(int i=1;i<=point;i++)
	{
		ans1=(ans1+minn[i]),ans2=(ans2*siz[i])%mod;
	}
	printf("%lld %lld",ans1,ans2%mod);
	return 0;
} 
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

P7687 [CEOI2005] Critical Network Lines割点但是难一些。

#include
using namespace std;
int n,m,len=0,last[5000001],low[5000001],dfsx[5000001],dfs_x=0;
int suma[5000001],sumb[5000001],ans=0,ans1[5000001],ans2[5000001],a,b;
struct pp
{
	int x,y,next;
};pp p[5000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int x,int fa)
{
	low[x]=dfsx[x]=++dfs_x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y])
		{
			CNT(y,x),low[x]=min(low[x],low[y]);
			if(low[y]>dfsx[x]&&(!suma[y]||!sumb[y]||(suma[y]==a)||(sumb[y]==b)))
			{
				ans++;ans1[ans]=y,ans2[ans]=x;	
			}
			suma[x]+=suma[y];sumb[x]+=sumb[y];
		}
		if(y!=fa) low[x]=min(low[x],dfsx[y]);
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(int i=1;i<=a;i++) 
	{
		int x;scanf("%d",&x);
		suma[x]++;
	}
	for(int i=1;i<=b;i++)
	{
		int x;scanf("%d",&x);
		sumb[x]++;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) CNT(i,i);	
	}
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}
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