tanjan2
基础
scc：强连通分量。
scc 缩点：得到的一定是 DAG（有向无环图）。
例题
HDU2767 Proving Equivalences
和昨天作业题相同。
对于缩点后的每个颜色，记录入度和出度。
随后，因为如果要全部称为强连通，就要所有入度和出度不为 0。
//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 = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct Edge
{
int v , nxt ;
}edge[500005];
struct node
{
int x , y ;
}Node[500005] ;
int n , m , scc , cnt , tim ;
int dfn[500005] , low[500005] , head[500005] , color[500005] , in[500005] , out[500005] ;
bool vis[500005] , res[500005] ;
stack<int> st ;
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 add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void tanjan(int u)
{
st.push(u) ;
vis[u] = 1 ;
dfn[u] = low[u] = ++tim ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(!dfn[v])
{
tanjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(vis[v] == 1)
{
low[u] = min(dfn[v] , low[u]) ;
}
}
if(dfn[u] == low[u])
{
scc++ ;
while(st.top() != u)
{
color[st.top()] = scc ;
vis[st.top()] = 0 ;
st.pop() ;
}
color[st.top()] = scc ;
vis[st.top()] = 0 ;
st.pop() ;
}
}
void init()
{
for( int i = 1 ; i <= n ; i++ ) head[i] = 0 ;
scc = tim = cnt = 0 ;
memset(vis , 0 , sizeof vis) ;
memset(dfn , 0 , sizeof dfn) ;
memset(low , 0 , sizeof low) ;
memset(in , 0 , sizeof in) ;
memset(out , 0 , sizeof out) ;
}
void work()
{
cin >> n >> m ;
init() ;
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) ;
}
}
for( int i = 1 ; i <= m ; i++ )
{
if(color[Node[i].x] != color[Node[i].y])
{
in[color[Node[i].y]]++ ;
out[color[Node[i].x]]++ ;
}
}
int ans1 = 0 , ans2 = 0 ;
for( int i = 1 ; i <= scc ; i++ )
{
if(in[i] == 0)
{
ans1++ ;
}
if(out[i] == 0)
{
ans2++ ;
}
}
cout << (scc == 1 ? 0 : max(ans1, ans2)) << "\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 ;
}P2272 [ZJOI2007] 最大半连通子图
发现每个点有两个度数：0 和 1。
所以本质就是个自动机。
给定一个起点，每次走一个边，答案就是这个边。
给定一个终点，到就输出。
//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 = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct Edge
{
int v , nxt ;
}edge[kMaxN] ;
struct node
{
int x , y ;
}Node[kMaxN] , Edge[kMaxN];
int n , m , x , scc , cnt , tim , ans ;
int dfn[kMaxN] , low[kMaxN] , head[kMaxN] , color[kMaxN] , in[kMaxN] , out[kMaxN] , siz[kMaxN] , g[kMaxN] , dp[kMaxN] ;
bool vis[kMaxN] , res[kMaxN] ;
stack<int> st ;
map<pair<int , int> , bool> mp ;
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 add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void tanjan(int u)
{
st.push(u) ;
vis[u] = 1 ;
dfn[u] = low[u] = ++tim ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(!dfn[v])
{
tanjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(vis[v] == 1)
{
low[u] = min(dfn[v] , low[u]) ;
}
}
if(dfn[u] == low[u])
{
scc++ ;
while(st.top() != u)
{
color[st.top()] = scc ;
vis[st.top()] = 0 ;
siz[scc]++ ;
st.pop() ;
}
color[st.top()] = scc ;
vis[st.top()] = 0 ;
siz[scc]++ ;
st.pop() ;
}
}
void topu()
{
queue<int> q ;
for( int i = 1 ; i <= scc ; i++ )
{
if(in[i] == 0)
{
q.push(i) ;
dp[i] = siz[i] ;
g[i] = 1 ;
}
}
while(!q.empty())
{
int u = q.front() ;
q.pop() ;
ans = max(ans , dp[u]) ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dp[v] == dp[u] + siz[v])
{
g[v] = (g[v] + g[u]) % x ;
}
else if(dp[v] < dp[u] + siz[v])
{
dp[v] = dp[u] + siz[v] ;
g[v] = g[u] % x ;
}
in[v]-- ;
if(in[v] == 0)
{
q.push(v) ;
}
}
}
}
bool cmp(node x , node y)
{
if(x.x != y.x) return x.x < y.x ;
else return x.y < y.y ;
}
void work()
{
cin >> n >> m >> x ;
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) ;
}
}
int num = 0 ;
for( int i = 1 ; i <= m ; i++ )
{
if(color[Node[i].x] != color[Node[i].y])
{
Edge[++num] = {color[Node[i].x] , color[Node[i].y]} ;
}
}
cnt = 0 ;
memset(head , 0 , sizeof head) ;
sort(Edge + 1 , Edge + num + 1 , cmp) ;
for( int i = 1 ; i <= num ; i++ )
{
if(Edge[i].x == Edge[i - 1].x && Edge[i].y == Edge[i - 1].y) continue ;
add_edge(Edge[i].x , Edge[i].y) ;
in[Edge[i].y]++ ;
}
topu() ;
cout << ans << "\n" ;
int res = 0 ;
for( int i = 1 ; i <= scc ; i++ )
{
if(dp[i] == ans)
{
res = (res + g[i]) % x ;
}
}
cout << res ;
}
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 ;
}