7.29tarjan专题测2
T1
割边模版，我没有想到不连通。
#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 55 ;
struct node
{
int v , nxt ;
}edge[kMaxN * kMaxN] ;
int low[kMaxN] , dfn[kMaxN] , head[kMaxN] ;
int n , m , res , tim , cnt = 1 ;
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
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(v == fa) continue ;
if(dfn[v] == 0)
{
tanjan(v , u) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] > dfn[u]) res++ ;
}
else
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void solve()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
add_edge(v , u) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0) tanjan(i , -1) ;
}
if(tim != n) cout << 0 ;
else cout << res ;
}
signed main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
// freopen("T1.in" , "r" , stdin) ;
// freopen("T1.out" , "w" , stdout) ;
int t = 1 ;
// cin >> t ;
while(t--) solve() ;
return 0 ;
}
T2
考试暴力，但是写炸了。
正解是 tanjan 拓扑找贡献。
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 5e4 + 10, Mod = 1e9;
int n , m , dfn[kMaxN] , low[kMaxN] , col[kMaxN] , scc , tim , in[kMaxN] , cnt[kMaxN] , dp[kMaxN] ;
bool vis[kMaxN] , vis1[kMaxN] , vis2[kMaxN] ;
vector<int> nbr[kMaxN] , re_nbr[kMaxN] ;
stack<int> stk ;
void tarjan(int u)
{
vis[u] = 1 ;
stk.push(u) ;
dfn[u] = low[u] = ++tim ;
for( int v : nbr[u] )
{
if (!dfn[v])
{
tarjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if (vis[v])
{
low[u] = min(low[u] , dfn[v]) ;
}
}
if (dfn[u] == low[u])
{
scc++ ;
while (!stk.empty())
{
col[stk.top()] = scc ;
vis[stk.top()] = 0 ;
if (stk.top() == u)
{
stk.pop() ;
break ;
}
stk.pop() ;
}
}
}
void bfs1()
{
queue<int> q ;
vis1[1] = 1 ;
q.push(1) ;
while (!q.empty())
{
int u = q.front() ;
q.pop() ;
for( int v : nbr[u] )
{
if (!vis1[v])
{
vis1[v] = 1 ;
q.push(v) ;
}
in[v]++ ;
}
}
}
void bfs2()
{
queue<int> q ;
vis2[2] = 1 ;
q.push(2) ;
while (!q.empty())
{
int u = q.front() ;
q.pop() ;
for( int v : re_nbr[u] )
{
if (!vis2[v])
{
vis2[v] = 1 ;
q.push(v) ;
}
}
}
}
void topo()
{
queue<int> q ;
dp[1] = 1 ;
q.push(1) ;
while (!q.empty())
{
int u = q.front() ;
q.pop() ;
for( int v : nbr[u] )
{
if (vis2[v])
{
long long sum = dp[v] + dp[u] ;
sum %= Mod ;
dp[v] = sum;
in[v]-- ;
if (!in[v]) q.push(v) ;
}
}
}
}
signed main() {
// freopen("T2.in", "r", stdin);
// freopen("T2.out", "w", stdout);
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
nbr[u].push_back(v) ;
re_nbr[v].push_back(u) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if (!dfn[i]) tarjan(i) ;
}
for( int i = 1 ; i <= n ; i++ )
{
cnt[col[i]]++ ;
}
bfs1() ;
bfs2() ;
for( int i = 1 ; i <= n ; i++ )
{
if (vis1[i] && vis2[i] && cnt[col[i]] != 1)
{
cout << "inf" ;
return 0 ;
}
}
topo() ;
cout << dp[2] ;
return 0;
}T3
这道题是最短路加割边。
最短路求出后，tanjan 看是否是割边。
#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 2e5 + 5 ;
struct Edge
{
int v , nxt , w ;
}edge[kMaxN * 2] ;
int low[kMaxN] , dfn[kMaxN] , ans[kMaxN] , dis[2][kMaxN] , head[kMaxN] , u[kMaxN] , v[kMaxN] , w[kMaxN] ;
bool vis[kMaxN] , bri[kMaxN * 2] ;
int n , m , res , tim , cnt ;
void add_edge(int u , int v , int w)
{
edge[++cnt] = {v , head[u] , w} ;
head[u] = cnt ;
}
struct node
{
int id ;
int w ;
bool operator < (const node & B) const
{
return w > B.w ;
}
};
priority_queue<node> Q ;
void dij(int s , int k)
{
fill(vis + 1 , vis + n + 1 , 0) ;
dis[k][s] = 0 ;
Q.push({s , 0}) ;
while(!Q.empty())
{
int u = Q.top().id ;
Q.pop() ;
if(vis[u]) continue ;
vis[u] = 1 ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dis[k][v] > dis[k][u] + edge[i].w)
{
dis[k][v] = dis[k][u] + edge[i].w ;
Q.push({v , dis[k][v]}) ;
}
}
}
}
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]) ;
if(low[v] > dfn[u])
{
bri[i] = bri[i ^ 1] = 1 ;
}
}
else if(i != fa)
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void solve()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
cin >> u[i] >> v[i] >> w[i] ;
add_edge(u[i] , v[i] , w[i]) ;
add_edge(v[i] , u[i] , w[i]) ;
}
memset(dis , 0x3f , sizeof dis) ;
dij(1 , 0) ;
dij(n , 1) ;
fill(head + 1 , head + n + 1 , 0) ;
cnt = 1 ;
for( int i = 1 ; i <= m ; i++ )
{
if((dis[0][u[i]] + dis[1][v[i]] + w[i] == dis[0][n]) || (dis[0][v[i]] + dis[1][u[i]] + w[i] == dis[0][n]))
{
vis[i] = 1 ;
add_edge(u[i] , v[i] , w[i]) ;
add_edge(v[i] , u[i] , w[i]) ;
ans[i] = cnt ;
}
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0)
{
tanjan(i , 0) ;
}
}
for( int i = 1 ; i <= m ; i++ )
{
if(ans[i] == 0)
{
cout << "No\n" ;
}
else
{
if(bri[ans[i]])
{
cout << "Yes\n" ;
}
else
{
cout << "No\n" ;
}
}
}
}
signed main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
// freopen("T3.in" , "r" , stdin) ;
// freopen("T3.out" , "w" , stdout) ;
int t = 1 ;
// cin >> t ;
while(t--) solve() ;
return 0 ;
}
T4
找出是否有交叉，有则分类讨论。