【算法提高——第三讲(二)】图论(2)

#include<bits/stdc++.h>
using namespace std;
const int N=40010,M=80010;
int n,m;
int fa[N][16],depth[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                fa[j][0]=t;
                q.push(j);
                for(int k=1;k<=15;k++)
                {
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }
    if(a==b) return a;
    for(int k=0;k<=15;k++)
    {
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    int root;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
        else
        {
            add(a,b),add(b,a);
        }
    }
    bfs(root);
    cin>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        if(p==a) cout<<1<<endl;
        else if(p==b) cout<<2<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;//first保存相关的查询节点编号，second保存查询编号
const int N=10010,M=20010;
int n,m;
int dis[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];
int h[N],e[M],w[M],ne[M],idx;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}
void dfs(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dis[j]=dis[u]+w[i];
        dfs(j,u);
    }
}
void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(int i=0;i<query[u].size();i++)
    {
        PII t=query[u][i];
        int y=t.first,id=t.second;
        if(st[y]==2)
        {
            int anc=findP(y);
            res[id]=dis[u]+dis[y]-2*dis[anc];
        }
    }
    st[u]=2;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a!=b)
        {
            query[a].push_back(make_pair(b,i));
            query[b].push_back(make_pair(a,i));
        }
    }
    for(int i=1;i<=n;i++) p[i]=i;
    dfs(1,-1);
    tarjan(1);
    for(int i=0;i<m;i++)
    {
        cout<<res[i]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010,M=300010,INF=0x3f3f3f3f;
int n,m;
int p[N];
int depth[N],fa[N][17],d1[N][17],d2[N][17];
int q[N];
struct Edge{
    int a,b,w;
    bool used;
    bool operator < (const Edge &t) const
    {
        return w<t.w;
    }
}edge[M];
int h[N],e[M],w[M],ne[M],idx;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}
LL kruskal()
{
    for(int i=1;i<=n;i++) p[i]=i;
    sort(edge,edge+m);
    LL res=0;
    for(int i=0;i<m;i++)
    {
        int a=findP(edge[i].a),b=findP(edge[i].b),w=edge[i].w;
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            edge[i].used=true;
        }
    }
    return res;
}
void build()
{
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        if(edge[i].used)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            add(a,b,w),add(b,a,w);
        }
    }
}
void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                d1[j][0]=w[i],d2[j][0]=-INF;
                for(int k=1;k<=16;k++)
                {
                    int anc=fa[j][k-1];
                    fa[j][k]=fa[anc][k-1];
                    int distance[4]={d1[j][k-1],d2[j][k-1],d1[anc][k-1],d2[anc][k-1]};
                    d1[j][k]=d2[j][k]=-INF;
                    for(int u=0;u<4;u++)
                    {
                        int d=distance[u];
                        if(d>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=d;
                        else if(d!=d1[j][k]&&d>d2[j][k]) d2[j][k]=d;
                    }
                }
            }
        }
    }
}
int lca(int a,int b,int w)
{
    static int distance[2*N];
    int cnt=0;
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
        {
            distance[cnt++]=d1[a][k];
            distance[cnt++]=d2[a][k];
            a=fa[a][k];
        }
    }
    if(a!=b)
    {
        for(int k=16;k>=0;k--)
        {
            if(fa[a][k]!=fa[b][k])
            {
                distance[cnt++]=d1[a][k];
                distance[cnt++]=d2[a][k];
                distance[cnt++]=d1[b][k];
                distance[cnt++]=d2[b][k];
                a=fa[a][k],b=fa[b][k];
            }
        }
        distance[cnt++]=d1[a][0];
        distance[cnt++]=d1[b][0];
    }
    int dist1=-INF,dist2=-INF;
    for(int i=0;i<cnt;i++)
    {
        int d=distance[i];
        if(d>dist1) dist2=dist1,dist1=d;
        else if(d!=dist1&&d>dist2) dist2=d;
    }
    if(w>dist1) return w-dist1;
    if(w>dist2) return w-dist2;
    return INF;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i].a=a,edge[i].b=b,edge[i].w=c;
    }
    LL sum=kruskal();
    build();
    bfs();
    LL res=1e18;
    for(int i=0;i<m;i++)
    {
        if(!edge[i].used)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            res=min(res,sum+lca(a,b,w));
        }
    }
    cout<<res;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=200010;
int n,m;
int depth[N],fa[N][17];
int d[N];
int ans;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=16;k++)
                {
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }
    if(a==b) return a;
    for(int k=16;k>=0;k--)
    {
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int dfs(int u,int father)
{
    int res=d[u];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            int s=dfs(j,u);
            if(s==0) ans+=m;
            else if(s==1) ans++;
            res+=s;
        }
    }
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bfs();
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        d[a]+=1,d[b]+=1,d[p]-=2;
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=50010;
int n,m;
int dfn[N],low[N],timestamp;
stack<int> stk;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int dout[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])
            low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk.top();
            stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;
        }
    }
    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            zeros++;
            sum+=sz[i];
            if(zeros>1)
            {
                sum=0;
                break;
            }
        }
    }
    cout<<sum;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10010;
int n;
int dfn[N],low[N],timestamp;
stack<int> stk;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int din[N],dout[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk.top();
            stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        while(true)
        {
            int b;
            cin>>b;
            if(b==0) break;
            add(i,b);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) din[b]++,dout[a]++;
        }
    }
    int p=0,q=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!din[i]) p++;
        if(!dout[i]) q++;
    }
    cout<<p<<endl;
    if(scc_cnt==1)
        cout<<0<<endl;
    else
        cout<<max(p,q)<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010,M=2000010;
int n,m,mod;
int dfn[N],low[N],timestamp;
stack<int> stk;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int f[N],g[N];
int h[N],hs[N],e[M],ne[M],idx;
void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk.top();
            stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    cin>>n>>m>>mod;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(h,a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    unordered_set<LL> S;
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            LL ha=a*1000000ll+b;
            if(a!=b&&!S.count(ha))
            {
                add(hs,a,b);
                S.insert(ha);
            }
        }
    }
    for(int i=scc_cnt;i>0;i--)
    {
        if(!f[i])
        {
            f[i]=sz[i];
            g[i]=1;
        }
        for(int j=hs[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            if(f[k]<f[i]+sz[k])
            {
                f[k]=f[i]+sz[k];
                g[k]=g[i];
            }
            else if(f[k]==f[i]+sz[k])
                g[k]=(g[k]+g[i])%mod;
        }
    }
    int maxf=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(f[i]>maxf)
        {
            maxf=f[i];
            sum=g[i];
        }
        else if(f[i]==maxf) sum=(sum+g[i])%mod;
    }
    cout<<maxf<<endl;
    cout<<sum<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010,M=600010;
int n,m;
int dfn[N],low[N],timestamp;
stack<int> stk;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int dis[N];
int h[N],hs[N],e[M],w[M],ne[M],idx;
void add(int h[],int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],dfn[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk.top();
            stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        add(h,0,i,1);
    while(m--)
    {
        int t,a,b;
        cin>>t>>a>>b;
        if(t==1) add(h,b,a,0),add(h,a,b,0);
        else if(t==2) add(h,a,b,1);
        else if(t==3) add(h,b,a,0);
        else if(t==4) add(h,b,a,1);
        else add(h,a,b,0);
    }
    tarjan(0);
    bool success=true;
    for(int i=0;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a==b)
            {
                if(w[j]>0)
                {
                    success=false;
                    break;
                }
            }
            else add(hs,a,b,w[j]);
        }
        if(!success) break;
    }
    if(!success) cout<<-1<<endl;
    else
    {
        for(int i=scc_cnt;i>0;i--)
        {
            for(int j=hs[i];j!=-1;j=ne[j])
            {
                int k=e[j];
                dis[k]=max(dis[k],dis[i]+w[j]);
            }
        }
        LL res=0;
        for(int i=1;i<=scc_cnt;i++) res+=(LL)dis[i]*sz[i];
        cout<<res;
    }
    return 0;
}