《季姬击鸡记》

赵元任

季姬寂，集鸡，鸡即棘鸡。棘鸡饥叽，季姬及箕稷济鸡。鸡既济，跻姬笈，季姬忌，急咭鸡，鸡急，继圾几，季姬急，即籍箕击鸡，箕疾击几伎，伎即齑，鸡叽集几基，季姬急极屐击鸡，鸡既殛，季姬激，即记《季姬击鸡记》

我的luogu博客

$$\Huge TYSC=TYSC+\sum_{i=2023}^{\infty}{me} $$

我的洛谷账号： 张晋嘉

我的oiclass（普及）账号： 张晋嘉

我的oiclass（入门）账号： 张晋嘉

燕子去了，关我什么事；杨柳枯了，关我什么事；桃花谢了，关我什么事。

强连通分量

int d[10005],l[10005],ans,n,m,x,y,c,s[10005],a[10005],sum;
vector<int> g[10005];
bool visit[10005];
stack<int> s1;
void tarjan(int u){
    d[u]=l[u]=++ans;
    s1.push(u);
    visit[u]=true;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(d[v]==-1) {
            tarjan(v);
            l[u]=min(l[u],l[v]);
        }else {
            if(visit[v]==true){
                l[u]=min(l[u],d[v]);
            }
        }
    }
    if(d[u]==l[u]){
        c++;
        int v;
        do{
            v=s1.top();
            s1.pop();
            s[v]=c;
            visit[v]=false;
        }while(u!=v);
    }
    return ;
}

判桥

int d[10005],l[10005],ans,n,m,x,y,c,s[10005],a[10005],sum;
vector<int> g[10005];
bool visit[10005];
stack<pair<int,int> > s1;
void tarjan(int u,int father){
	c=0; 
    d[u]=l[u]=++ans;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(d[v]==0) {
        	c++;
            tarjan(v,u);
            l[u]=min(l[u],l[v]);
            if(l[v]>=d[u]) visit[u]=true;
            if(l[v]>d[u]) s1.push(make_pair(u,v));
        }else {
            if(d[v]<d[u]&&v!=father) l[u]=min(l[u],d[v]);
        }
    }
    if(father<0&&c=1) visit[u]=false;
}

判重边桥

int d[10005],l[10005],ans,n,m,x,y,c,s[10005],a[10005],sum,data[10005],next[10005],h[10005];
bool visit[10005];
stack<pair<int,int> > s1;
void add(int u,int v){
	data[++sum]=v;
	next[sum]=h[u];
	h[u]=sum;
}
void tarjan(int u,int father){
    d[u]=l[u]=++ans;
    for(int i=h[u];i!=-1;i=next[i]){
        int v=data[i];
        if(i==(father^ans)) continue;
        if(d[v]==0) {
            tarjan(v,i);
            l[u]=min(l[u],l[v]);
            if(l[v]>d[u]) cout<<u<<" "<<v<<endl;
        }else {
            l[u]=min(l[u],d[v]);
        }
    }
}

void Floyd(){ 
    for(int k=1;k<=n;k++){ 
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=n;j++){ 
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 
            } 
        } 
    } 
}

flody

#include <bits/stdc++.h>
using namespace std;
int d[10005],l[10005],ans,n,m,x,y,c,s[10005],a[10005],sum;
vector<int> g[10005];
bool visit[10005];
stack<int> s1;
void tarjan(int u){
    d[u]=l[u]=++ans;
    s1.push(u);
    visit[u]=true;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(d[v]==-1) {
            tarjan(v);
            l[u]=min(l[u],l[v]);
        }else {
            if(visit[v]==true){
                l[u]=min(l[u],d[v]);
            }
        }
    }
    if(d[u]==l[u]){
        c++;
        int v;
        do{
            v=s1.top();
            s1.pop();
            s[v]=c;
            visit[v]=false;
        }while(u!=v);
    }
    return ;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        g[x].push_back(y);
    }
    memset(d,-1,sizeof(d));
    tarjan(1);
    for(int i=1;i<=n;i++){
        if(s[i]==0){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        //cout<<s[i]<<" ";
        a[s[i]]++;
    }
    //cout<<endl;
    for(int i=1;i<=c;i++){
        if(a[i]>1){
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

tarjan

void tarjan(int u){
	int c=0; 
    d[u]=l[u]=++ans;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(d[v]==0) {
            tarjan(v);
            l[u]=min(l[u],l[v]);
            if(l[v]>=d[u]){
                c++;
                if(u!=1||c>1) a[u]=1;
            }
        }else {
            l[u]=min(d[v],l[u]);
        }
    }
}

割点