tarjan专题测
T1
tanjan 模版，看是否有一个强连通大小大于一。
//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define ll long long
using namespace std ;
const int kMaxN = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct node
{
int v , nxt ;
}edge[kMaxN] ;
int n , m ;
int siz[kMaxN] , dfn[kMaxN] , low[kMaxN] , head[kMaxN] , tim , cnt , scc ;
bool vis[kMaxN] ;
stack<int> st ;
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void tanjan(int u)
{
dfn[u] = low[u] = ++tim ;
vis[u] = 1 ;
st.push(u) ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dfn[v] == 0)
{
tanjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(vis[v])
{
low[u] = min(low[u] , dfn[v]) ;
}
}
if(low[u] == dfn[u])
{
scc++ ;
while(!st.empty())
{
vis[st.top()] = 0 ;
siz[scc]++ ;
if(u == st.top())
{
st.pop() ;
break ;
}
st.pop() ;
}
}
}
void work()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0)
{
tanjan(i) ;
}
}
for( int i = 1 ; i <= scc ; i++ )
{
if(siz[i] > 1)
{
cout << "Yes\n" ;
return ;
}
}
cout << "No\n" ;
}
signed main()
{
// freopen("T1.in" , "r" , stdin) ;
// freopen("T1.out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
T2
这题是强连通分量的拓展缩点，发现一个强连通分量所有点都可以到，所以可以看作一个点。
这样再进行一个树上 DP。对于一个点任意儿子，他都可以到达，所以需要
//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define ll long long
using namespace std ;
const int kMaxN = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct node
{
int v , nxt ;
}edge[100005] ;
struct edge
{
int u , v ;
}Node[100005] ;
int n , m ;
int color[kMaxN] , siz[kMaxN] , dfn[kMaxN] , low[kMaxN] , head[kMaxN] , dp[kMaxN] , tim , cnt , scc ;
bool vis[kMaxN] ;
stack<int> st ;
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void tanjan(int u)
{
dfn[u] = low[u] = ++tim ;
vis[u] = 1 ;
st.push(u) ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dfn[v] == 0)
{
tanjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(vis[v])
{
low[u] = min(low[u] , dfn[v]) ;
}
}
if(low[u] == dfn[u])
{
scc++ ;
while(!st.empty())
{
vis[st.top()] = 0 ;
siz[scc]++ ;
color[st.top()] = scc ;
if(u == st.top())
{
st.pop() ;
break ;
}
st.pop() ;
}
}
}
void dfs(int u)
{
if(dp[u] != -1) return ;
dp[u] = siz[u] ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dp[v] == -1) dfs(v) ;
dp[u] += dp[v] ;
}
}
void work()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
Node[i] = {u , v} ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0)
{
tanjan(i) ;
}
}
cnt = 0 ;
memset(head , 0 , sizeof head) ;
for( int i = 1 ; i <= m ; i++ )
{
if(color[Node[i].u] != color[Node[i].v])
{
add_edge(color[Node[i].u] , color[Node[i].v]) ;
}
}
memset(dp , -1 , sizeof dp) ;
for( int i = 1 ; i <= scc ; i++ )
{
if(dp[i] == -1)
{
dfs(i) ;
}
}
for( int i = 1 ; i <= n ; i++ )
{
cout << dp[color[i]] - 1 << "\n" ;
}
}
signed main()
{
// freopen("T2.in" , "r" , stdin) ;
// freopen("T2.out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
T3
割边。
对于每个点，都加上儿子能收到的信息数，判断即可。
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
string s=#__VA_ARGS__,s2="";\
vector<string>v;\
for(auto i:s){\
if(i==','){\
v.push_back(s2);\
s2="";\
}else{\
s2+=i;\
}\
}\
v.push_back(s2);\
vector<int>v2={__VA_ARGS__};\
for(int i=0;i<v.size()-1;i++){\
cout<<v[i]<<"="<<v2[i]<<"\n";\
}\
cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 2e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct node
{
int v , nxt ;
}edge[kMaxN] ;
int n , m , k , l , tim , cnt = 1 ;
int a[kMaxN] , b[kMaxN] , dfn[kMaxN] , low[kMaxN] , head[kMaxN] ;
vector<pair<int , int> > ans ;
inline ll ksm(ll a , ll b)
{
ll mul = 1 ;
while(b)
{
if(b & 1) mul *= a , mul %= MOD ;
a *= a ;
a %= MOD ;
b >>= 1 ;
}
return mul ;
}
inline int read()
{
int x = 0 , f = 1 ;
char ch = getchar() ;
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1 ;
ch = getchar() ;
}
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
return x * f ;
}
void write(int x)
{
if(x < 0) putchar('-') , x = -x ;
if(x > 9) write(x / 10) ;
putchar(x % 10 + '0') ;
}
void tanjan(int u , int fa)
{
dfn[u] = low[u] = ++tim ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dfn[v] == 0)
{
tanjan(v , i ^ 1) ;
low[u] = min(low[u] , low[v]) ;
a[u] += a[v] ;
b[u] += b[v] ;
if(low[v] > dfn[u] && ((!a[v] || a[v] == k) || (!b[v] || b[v] == l)))
{
ans.push_back({u , v}) ;
}
}
else if(i != fa)
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void work()
{
cin >> n >> m >> k >> l ;
for( int i = 1 ; i <= k ; i++ )
{
int x ;
cin >> x ;
a[x] = 1 ;
}
for( int i = 1 ; i <= l ; i++ )
{
int x ;
cin >> x ;
b[x] = 1 ;
}
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
add_edge(v , u) ;
}
tanjan(1 , 0) ;
cout << ans.size() << "\n" ;
for( int i = 0 ; i < ans.size() ; i++ )
{
cout << ans[i].first << " " << ans[i].second << "\n" ;
}
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
T4
记录反边和正边，进行拓扑。
#include<bits/stdc++.h>
using namespace std;
int n , m ;
int dfn[100005] , low[100005] , cnt ;
bool inst[100005] ;
int st[100005] , top , scc[100005] , tot , siz[100005] ;
int in[100005][2] , dp[100005][2] ;
vector<int>g[100005] , e[100005][2] ;
void tanjan(int u)
{
dfn[u] = low[u] = ++cnt ;
st[++top] = u ;
inst[u] = 1 ;
for( auto i : g[u] )
{
if(!dfn[i])
{
tanjan(i) ;
low[u] = min(low[u] , low[i]) ;
}
else if(inst[i])
{
low[u] = min(low[u] , dfn[i]) ;
}
}
if(dfn[u]==low[u])
{
tot++ ;
do
{
scc[st[top]] = tot ;
inst[st[top]] = 0 ;
siz[tot]++ ;
}while(st[top--] != u);
}
}
void topu(int k)
{
queue<int> q ;
dp[scc[1]][k] = siz[scc[1]] ;
for( int i = 1 ; i <= tot ; i++ )
{
if(!in[i][k])
{
q.push(i) ;
}
}
while(q.size())
{
int u = q.front() ;
q.pop() ;
for( auto i : e[u][k] )
{
dp[i][k] = max(dp[i][k] , dp[u][k] + siz[i]) ;
in[i][k]-- ;
if(!in[i][k])
{
q.push(i) ;
}
}
}
}
signed main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
g[u].push_back(v) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(!dfn[i])
{
tanjan(i) ;
}
}
int ans = siz[scc[1]] ;
for( int i = 1 ; i <= n ; i++ )
{
for( auto j : g[i] )
{
if(scc[i] != scc[j])
{
e[scc[i]][0].push_back(scc[j]) ;
e[scc[j]][1].push_back(scc[i]) ;
in[scc[j]][0]++ ;
in[scc[i]][1]++ ;
}
}
}
memset(dp , -0x3f , sizeof(dp)) ;
topu(0) ;
topu(1) ;
for( int i = 1 ; i <= n ; i++ )
{
for( auto j : g[i] )
{
if(scc[i] != scc[j])
{
ans = max(ans , dp[scc[j]][0] + dp[scc[i]][1] - siz[scc[1]]) ;
}
}
}
cout << ans ;
return 0 ;
}