有向图缩点题集

有向图缩点的复习 算是 （纠正一些写法

有向图缩点板子

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first 
#define y second
#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
int m;
int cnt;
vector<vector<int>>scc;
int dfn[N];
int low[N];
stack<int>s;
vector<int>g[N];
int ins[N];
int bel[N];
int idx;
void dfs(int u)
{
	dfn[u]=low[u]=++idx;
	s.push(u);
	ins[u]=1;
	for(auto v:g[u])
	{
	 if(!dfn[v])dfs(v);
	 if(ins[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		vector<int>c;
		++cnt;
		while(true)
		{
			int v=s.top();
			c.pb(v);
			ins[v]=0;
			bel[v]=cnt;
			s.pop();
			if(v==u)break;
		}
		sort(c.begin(),c.end());
		scc.pb(c);
	}
}
void solve()
{
	cin>>n>>m;
	fer(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
	//	g[b].pb(a);
	}
	fer(i,1,n)
	{
		if(!dfn[i])dfs(i);
	}
	sort(scc.begin(),scc.end());
    for (auto c : scc) {
		for (auto u : c) printf("%d ", u);
		puts("");
	} 
}

signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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

HAOI2006, 受欢迎的牛

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first 
#define y second
#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
int m;
int cnt;
vector<vector<int>>scc;
int dfn[N];
int low[N];
stack<int>s;
vector<int>g[N];
int ins[N];
int bel[N];
int sz[N];
int out[N];
int idx;
void dfs(int u)
{
	dfn[u]=low[u]=++idx;
	s.push(u);
	ins[u]=1;
	for(auto v:g[u])
	{
	 if(!dfn[v])dfs(v);
	 if(ins[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		++cnt;
		while(true)
		{
			int v=s.top();
			ins[v]=0;
			bel[v]=cnt;
			sz[cnt]++;
			s.pop();
			if(v==u)break;
		}
	}
}
void solve()
{
	cin>>n>>m;
	fer(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
	//	g[b].pb(a);
	}
	fer(i,1,n)
	{
		if(!dfn[i])dfs(i);
	}
	fer(i,1,n)
	for(auto v:g[i]){
		if(bel[v]!=bel[i])out[bel[i]]++;
	}
	int cnt1=0;
	int cnt2=0;
//	cout<<cnt<<endl;
	fer(i,1,cnt)
	{
		if(out[i]==0)cnt1++,cnt2+=sz[i];
	}
	if(cnt1>=2)puts("0");
	else cout<<cnt2<<endl;
    
}

signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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

最大半连通子图 （经典缩点dp最长路

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first 
#define y second
#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
//const int mod=1e9+7;
int mod;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
int m;
int cnt;
int dfn[N];
int low[N];
stack<int>s;
vector<int>g[N];
int ins[N];
int bel[N];
int sz[N];
int out[N];
int idx;
int dp[N];
int ans1;
int ans2;
int vis[N];
int way[N];
void dfs(int u)
{
	dfn[u]=low[u]=++idx;
	s.push(u);
	ins[u]=1;
	for(auto v:g[u])
	{
	 if(!dfn[v])dfs(v);
	 if(ins[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		++cnt;
		int sz=0;
		dp[cnt]=0;
		way[cnt]=1;
		while(true)
		{
			int v=s.top();
			ins[v]=0;
			bel[v]=cnt;
			sz++;
			for(int w:g[v])
			{
			  if(vis[bel[w]]!=cnt&&bel[w]!=0)
			{
				if(dp[bel[w]]>dp[cnt])
				{
					dp[cnt]=dp[bel[w]];
					way[cnt]=0;
				}
				if(dp[bel[w]]==dp[cnt])
				{
					way[cnt]=(way[cnt]+way[bel[w]])%mod;
				}
			}	
			}
			s.pop();
			if(v==u)break;
		}
		dp[cnt]+=sz;
		if(dp[cnt]>ans1)ans1=dp[cnt],ans2=0;
		if(dp[cnt]==ans1)ans2=(ans2+way[cnt])%mod;
	}
}
void solve()
{
	cin>>n>>m>>mod;
	fer(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
	//	g[b].pb(a);
	}
	fer(i,1,n)
	{
		if(!dfn[i])dfs(i);
	}
    cout<<ans1<<endl;
	cout<<ans2<<endl; 
}

signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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
107
108
109
110
111
112
113
114
115
116

APIO2009, ATM

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first 
#define y second
#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
//const int mod=1e9+7;
int mod;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=5e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
int m;
int cnt;
int dfn[N];
int low[N];
stack<int>s;
vector<int>g[N];
int ins[N];
int bel[N];
int idx;
int a[N];
int dp[N];
int bar[N];
int ss,t;
void dfs(int u)
{
	dfn[u]=low[u]=++idx;
	s.push(u);
	ins[u]=1;
	for(auto v:g[u])
	{
	 if(!dfn[v])dfs(v);
	 if(ins[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		++cnt;
		int val=0;
		bool sbar=false;
		dp[cnt]=-inf;
		while(true)
		{
			int v=s.top();
		    ins[v]=false;
		    bel[v]=cnt;
		    val+=a[v];
		    sbar|=bar[v];
		    for(int w:g[v])
		    {
		    	if(bel[w]!=cnt&&bel[w]!=0)
		    	dp[cnt]=max(dp[cnt],dp[bel[w]]);
			}
			s.pop();
			if(u==v)break;
		}
		if(sbar)dp[cnt]=max(dp[cnt],(int)0);
		dp[cnt]+=val;
	}
}
void solve()
{
	cin>>n>>m;
	fer(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
	//	g[b].pb(a);
	}
    fer(i,1,n)cin>>a[i];
    cin>>ss>>t;
    fer(i,1,t)
    {
    	int x;
    	cin>>x;
    	bar[x]=1;
	}
	dfs(ss);

//	cout<<cnt<<endl;
	cout<<dp[bel[ss]]<<endl;
}

signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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
107
108
109

SDOI2010, 所驼门王的宝藏

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
//#define x first 
//#define y second
#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
//const int mod=1e9+7;
int mod;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=5e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
int m;
int cnt;
int dfn[N];
int low[N];
stack<int>s;
vector<int>g[N];
int ins[N];
int bel[N];
int idx;
int dp[N];

map<pii,int>id;
map<int,vector<int>>r,c;
map<int,int>cid,rid;
int ty[N];
int R,C;
int ans;
int x[N];
int y[N];
void dfs(int u)
{
	dfn[u]=low[u]=++idx;
	s.push(u);
	ins[u]=1;
	for(auto v:g[u])
	{
	 if(!dfn[v])dfs(v);
	 if(ins[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		++cnt;
		int val=0;
		dp[cnt]=0;
		while(true)
		{
			int v=s.top();
		    ins[v]=false;
		    bel[v]=cnt;
		    val+=(v<=n);
		    for(int w:g[v])
		    {
		    	if(bel[w]!=cnt&&bel[w]!=0)
		    	dp[cnt]=max(dp[cnt],dp[bel[w]]);
			}
			s.pop();
			if(u==v)break;
		}
		dp[cnt]+=val;
		ans=max(ans,dp[cnt]);
	}
}
void solve()
{
	cin>>n>>R>>C;
	fer(i,1,n)
	{
		cin>>x[i]>>y[i]>>ty[i];
		id[{x[i],y[i]}]=i;
		r[x[i]].pb(i);
		c[y[i]].pb(i);
	}
	int tot=n;
	fer(i,1,n)
	{
	if(ty[i]==1){
	    if(!rid.count(x[i])){
		rid[x[i]]=++tot;
		for(auto id:r[x[i]]) g[tot]	.pb(id);
    }
	g[i].pb(rid[x[i]]);	
	}
	else if(ty[i]==2)
	{
		if(!cid.count(y[i])){
			cid[y[i]]=++tot;
			for(auto id:c[y[i]])g[tot].pb(id);
		}
		g[i].pb(cid[y[i]]);	
	}
	else if(ty[i]==3)
	{
		for (int dx = -1; dx <= 1; dx++)
				for (int dy = -1; dy <= 1; dy++) {
					if (dx == 0 && dy == 0) continue;
					if (!id.count({x[i]+dx,y[i] + dy})) continue;
					g[i].pb(id[{x[i] + dx, y[i] + dy}]);
	}
	}
    }
    fer(i,1,tot)
    {
    	if(!dfn[i])dfs(i);
	}
	cout<<ans<<endl;
}

signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

USACO2015 Jan, Grass Cownoisseur

#include <bits/stdc++.h>
using namespace  std;
#define  int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first 
#define y second
//#define pb  push_back
#define inf 1e18
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--) 
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b)
{int res=1;  while(b){  if(b&1) res=res*a%mod;  a=a*a%mod;  b>>=1; } return res;}
const int N=2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
vector<int>cc[N];
int cnt;
int idx;
int dfn[N],low[N],ins[N],bel[N];
stack<int>s;
int m;
int sz[N];
vector<int>g[N];
vector<int>rg[N];
int f1[N];
int f2[N];
void dfs(int u)
{
   dfn[u]=low[u]=++idx;
   s.push(u);
   ins[u]=true;
   for(auto v:g[u])
   {
    if(!dfn[v])dfs(v);
	if(ins[v])low[u]=min(low[u],low[v]);	
   }
   if(dfn[u]==low[u]){
   	++cnt;
   	while(true){
   		//++cnt;
   		int v=s.top();
   		ins[v]=false;
   		bel[v]=cnt;
   		sz[cnt]++;
   		cc[cnt].push_back(v);
   		s.pop();
   		if(u==v)break;
	   }
   }	
} 

void solve()
{
	cin>>n>>m;
	fer(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		rg[b].push_back(a);
	}
	fer(i,1,n)
	{
		if(!dfn[i])dfs(i);
	}
	fer(i,1,cnt)f1[i]=f2[i]=-inf;
	int s=bel[1];
	f2[s]=f1[s]=sz[s];
	der(i,s-1,1)
	{
		for(auto u:cc[i]){
		for(auto v:rg[u])if(bel[v]>bel[u])f1[i]=max(f1[i],f1[bel[v]]+sz[i]);
		}	
	}
	fer(i,s+1,cnt)
	{
		for(auto u:cc[i]){
			for(auto v:g[u])if(bel[v]<bel[u])f2[i]=max(f2[i],f2[bel[v]]+sz[i]);
		}
	}
	int ans=sz[s];
	fer(i,s,cnt){
		for(auto u:cc[i])
		{
		for(auto v:g[u]){
			if(bel[v]<=s)ans=max(ans,f2[i]+f1[bel[v]]-sz[s]);
		}
	}
	}
	cout<<ans<<endl;
}
signed main()
{
	IOS;
	int _=1;
	//cin>>_;
	while(_--) solve();
	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
107
108
109
110
111
112