今天讲的是图论大体上分为：有向图的强连通分量，有向图的完全图：竞赛图，无向图的的割点，割边，点双联通分量，变双联通分量以及圆方树 2-sat问题 支配树等等。

大体上都知道是些什么东西 但是仍需要写一些东西来好好巩固一下基础。太菜了 加油！。

1 有向图的强联通分量 写过好多次了 判断条件为dfn[x]==low[x] 此时栈中的所有点形成一个强连通分量。

bzoj 最受欢迎的牛：

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=50010;
int n,m,len,cnt,top,num;
struct wy
{
    int x,y;
}t[MAXN];
int c[MAXN],b[MAXN],out[MAXN];
int lin[MAXN],nex[MAXN],ver[MAXN];
int s[MAXN],dfn[MAXN],low[MAXN],vis[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void dfs(int x)
{
    dfn[x]=low[x]=++cnt;
    s[++top]=x;vis[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(!dfn[tn])
        {
            dfs(tn);
            low[x]=min(low[x],low[tn]);
        }
        else if(vis[tn])low[x]=min(low[x],dfn[tn]);
    }
    //cout<<x<<' '<<dfn[x]<<' '<<low[x]<<endl;
    if(dfn[x]==low[x])
    {
        int y;++num;
        //cout<<x<<endl;
        do
        {
            y=s[top--];
            c[y]=num;++b[num];
            vis[y]=0;
        }
        while(y!=x);
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        t[i].x=read();
        t[i].y=read();
        add(t[i].x,t[i].y);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
    //cout<<num<<endl;
    for(int i=1;i<=n;++i)
        for(int j=lin[i];j;j=nex[j])
        {
            int tn=ver[j];
            if(c[tn]==c[i])continue;
            ++out[c[i]];
        }
    int flag=0;
    for(int i=1;i<=num;++i)
    {
        if(out[i]==0&&flag)
        {
            puts("0");
            return 0;
        }
        if(out[i]==0&&flag==0)flag=b[i];
    }
    printf("%d\n",flag);
    return 0;
}

View Code

杀人游戏：

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=300010;
int n,m,len,cnt,top,num,sum,flag,len1;
int lin[MAXN],ver[MAXN],nex[MAXN],out[MAXN];
int lin1[MAXN],ver1[MAXN],nex1[MAXN];
int vis[MAXN],s[MAXN];
int dfn[MAXN],low[MAXN],b[MAXN],c[MAXN],in[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void add1(int x,int y)
{
    ver1[++len1]=y;
    nex1[len1]=lin1[x];
    lin1[x]=len1;
}
inline void dfs(int x)
{
    dfn[x]=low[x]=++cnt;
    s[++top]=x;vis[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(!dfn[tn])
        {
            dfs(tn);
            low[x]=min(low[x],low[tn]);
        }
        else if(vis[tn])low[x]=min(low[x],dfn[tn]);
    }
    if(dfn[x]==low[x])
    {
        ++num;int y;
        do
        {
            y=s[top];--top;
            c[y]=num;++b[num];
            vis[y]=0;
        }
        while(x!=y);
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int x,y;
        x=read();y=read();
        add(x,y);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
    //cout<<num<<endl;
    for(int i=1;i<=n;++i)
    {
        for(int j=lin[i];j;j=nex[j])
        {
            int tn=ver[j];
            if(c[i]==c[tn])continue;
            //cout<<c[tn]<<' '<<i<<endl;
            add1(c[i],c[tn]);
            ++in[c[tn]];++out[c[i]];
        }
    }
    for(int i=1;i<=num;++i)
    {
        if(!in[i])++sum;
        if(!in[i]&&!out[i]&&b[i]==1)flag=1;
        if(!in[i]&&b[i]==1)
        {
            int mark=0;
            for(int j=lin1[i];j;j=nex1[j])
            {
                int tn=ver1[j];
                if(in[tn]==1)mark=1;
            }
            if(!mark)flag=1;
        }
    }
    printf("%.6lf\n",(n-sum+flag)*1.0/(n*1.0));
    return 0;
}

View Code

推荐一写 细节非常之多。

炸弹游戏 线段树优化建图+强连通分量。

线段树优化建图的话 我认为是 将一个点向一个区间整体连边 可转换成线段树上的连边 原因 我们不知道哪一条边起到了连接强连通分量的作用。

所以采用线段树优化一下边数至多为 2n+nlogn.

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
#define INF 5000000000000000000ll
#define l(x) t[x].l
#define r(x) t[x].r
#define mn(x) t[x].mn
#define mx(x) t[x].mx
#define ll long long
#define mod 1000000007
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=500010;
int n,cnt,top,root,num,len,len1,T,h,w;
ll ans,vmn[MAXN<<1],vmx[MAXN<<1];
int ru[MAXN<<1],q[MAXN<<1];
int pos[MAXN],dfn[MAXN<<1],low[MAXN<<1],s[MAXN<<1];
int vis[MAXN<<1],c[MAXN<<1];
int lin[MAXN<<1],ver[MAXN*20],nex[MAXN*20];
int lin1[MAXN<<1],ver1[MAXN*20],nex1[MAXN*20];
ll a[MAXN],b[MAXN];
struct wy//动态开点线段树 优化建图
{
    int l,r;
    ll mn,mx;
}t[MAXN<<1];
inline void add(int x,int y)
{
    ver[++len]=y;nex[len]=lin[x];lin[x]=len;
}
inline void add1(int x,int y)
{
    ver1[++len1]=y;nex1[len1]=lin1[x];lin1[x]=len1;
}
inline void tarjan(int x)
{
    dfn[x]=low[x]=++w;
    s[++top]=x;vis[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(!dfn[tn])
        {
            tarjan(tn);
            low[x]=min(low[x],low[tn]);
        }
        else if(vis[tn])low[x]=min(low[x],dfn[tn]);
    }
    if(dfn[x]==low[x])
    {
        ++num;int y;
        vmn[num]=INF;vmx[num]=-INF;
        do
        {
            y=s[top--];
            vis[y]=0;c[y]=num;
            vmn[num]=min(vmn[num],mn(y));
            vmx[num]=max(vmx[num],mx(y));
        }
        while(x!=y);
    }
}
inline void build(int &p,int l,int r)
{
    if(!p)p=++cnt;
    if(l==r)
    {
        pos[l]=p;
        mn(p)=a[l];mx(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
    mn(p)=min(mn(l(p)),mn(r(p)));
    mx(p)=max(mx(l(p)),mx(r(p)));
    add(p,l(p));add(p,r(p));
}
inline void change(int p,int L,int R,int l,int r,int x)
{
    if(L<=l&&R>=r)
    {
        add(x,p);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)change(l(p),L,R,l,mid,x);
    if(R>mid)change(r(p),L,R,mid+1,r,x);
}
inline void topsort()
{
    while(h++<T)
    {
        int x=q[h];
        for(int i=lin1[x];i;i=nex1[i])
        {
            int tn=ver1[i];
            --ru[tn];
            vmn[tn]=min(vmn[tn],mn(x));
            vmx[tn]=max(vmx[tn],mx(x));
            if(!ru[tn])q[++T]=tn;
        }
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
    build(root,1,n);
    for(int i=1;i<=n;++i)
    {
        int l=lower_bound(a+1,a+1+n,a[i]-b[i])-a;//这个一定不会越界
        int r=upper_bound(a+1,a+1+n,a[i]+b[i])-a-1;//这个有可能会越界但是不会出错
        //cout<<l<<' '<<r<<endl;
        //cout<<pos[i]<<endl;
        change(root,l,r,1,n,pos[i]);
    }
    //cout<<cnt<<endl;
    for(int i=1;i<=cnt;++i)if(!dfn[i])tarjan(i);
    //printf("%d\n",num);
    //cout<<(ll)num<<endl;
    for(int i=1;i<=cnt;++i)
    {
        for(int j=lin[i];j;j=nex[j])
        {
            int tn=ver[j];
            if(c[i]==c[tn])continue;
            add1(c[tn],c[i]);++ru[c[i]];
        }
    }
    for(int i=1;i<=num;++i)if(!ru[i])q[++T]=c[i];
    topsort();
    for(int i=1;i<=n;++i)
    {
        int l=lower_bound(a+1,a+1+n,vmn[c[pos[i]]])-a;
        int r=upper_bound(a+1,a+1+n,vmx[c[pos[i]]])-a-1;
        ans+=(ll)(r-l+1)*(ll)i%mod;
    }
    printf("%lld\n",ans%mod);
    return 0;
}

View Code

割点：BLO 以前的代码。

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cctype>
#include<utility>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<cstdlib>
#define INF 2147483646
#define ll long long
#define db double
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(ll x)
{
    x<0?putchar('-'),x=-x:0;
    ll num=0;char ch[70];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('\n');return;
}
const ll MAXN=500002;
ll n,m,num;
ll ans[MAXN],dfn[MAXN],low[MAXN],cut[MAXN];
ll sz[MAXN];//s[i]表示以i为根节点的子树大小
ll lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1],len;
inline void add(ll x,ll y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline ll min(ll x,ll y){return x>y?y:x;}
void tarjan(ll x)
{
    dfn[x]=low[x]=++num;
    sz[x]=1;ll flag=0,sum=0;
    for(ll i=lin[x];i;i=nex[i])
    {
        ll tn=ver[i];
        if(!dfn[tn])
        {
            tarjan(tn);
            sz[x]+=sz[tn];
            low[x]=min(low[x],low[tn]);
            if(low[tn]==dfn[x])
            {
                flag++;
                if(x!=1||flag>1)
                {
                    cut[x]=1;sum+=sz[tn];
                    ans[x]+=sz[tn]*(n-sz[tn]-1);
                }
            }
        }
        else low[x]=min(low[x],dfn[tn]);
    }
    if(cut[x])ans[x]+=(n-sum-1)*sum;
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(ll i=1;i<=m;++i)
    {
        ll x,y;
        x=read();y=read();
        add(x,y);add(y,x);
    }
    tarjan(1);
    for(ll i=1;i<=n;++i)put(ans[i]+(n-1)*2);
    return 0;
}

View Code

bzoj 3331 圆方树+树上差分 非常简单。

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
#define INF 5000000000000000000ll
#define l(x) t[x].l
#define r(x) t[x].r
#define mn(x) t[x].mn
#define mx(x) t[x].mx
#define ll long long
#define mod 1000000007
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=200010,maxn=MAXN<<2;
int n,m,k,len,top,num,cnt,T;
int dfn[MAXN],low[MAXN],s[MAXN];
int lin[maxn],ver[maxn],nex[maxn];
int f[MAXN<<1][21],d[MAXN<<1],c[MAXN<<1];
vector<int>g[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++cnt;
    s[++top]=x;
    for(unsigned int i=0;i<g[x].size();++i)
    {
        int tn=g[x][i];
        if(!dfn[tn])
        {
            tarjan(tn);
            low[x]=min(low[x],low[tn]);
            if(dfn[x]==low[tn])
            {
                ++num;
                for(int j=0;j!=tn;--top)
                {
                    j=s[top];
                    add(num,j);
                    add(j,num);
                }
                add(num,x);
                add(x,num);
            }
        }
        else low[x]=min(low[x],dfn[tn]);
    }
}
inline void dfs(int x,int father)
{
    d[x]=d[father]+1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(tn==father)continue;
        f[tn][0]=x;
        for(int j=1;j<=T;++j)f[tn][j]=f[f[tn][j-1]][j-1];
        dfs(tn,x);
    }
}
inline int LCA(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    for(int i=T;i>=0;--i)
        if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=T;i>=0;--i)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void dfs(int x)
{
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(tn==f[x][0])continue;
        dfs(tn);
        c[x]+=c[tn];
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();k=read();
    for(int i=1;i<=m;++i)
    {
        int x,y;
        x=read();y=read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    num=n;tarjan(1);
    //cout<<num<<endl;
    T=(int)(log((n+num)*1.0)/log(2.0))+1;
    dfs(1,0);
    //for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i),--top;
    for(int i=1;i<=k;++i)
    {
        int x,y;
        x=read();y=read();
        int lca=LCA(x,y);
        ++c[x];++c[y];
        --c[lca];
        if(f[lca][0])--c[f[lca][0]];
    }
    dfs(1);
    for(int i=1;i<=n;++i)printf("%d\n",c[i]);
    return 0;
}

View Code

luogu 4630 铁人两项

圆方树 + 特殊性质 +树形dp 想的还不是很成熟。

总之符合路径的一定是s 到 f 路径上的 圆点和方点 采用树形dp O(n)解决。

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
#define INF 1000000000
#define ll long long
#define mod 1000000007
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=100005,maxn=MAXN<<2;
int n,m,k,len,top,num,cnt,sz;
ll ans;
int dfn[MAXN],low[MAXN],s[MAXN],w[MAXN<<1];
int lin[maxn],ver[maxn],nex[maxn],b[MAXN<<1];
vector<int>g[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++cnt;
    s[++top]=x;++sz;
    for(unsigned int i=0;i<g[x].size();++i)
    {
        int tn=g[x][i];
        if(!dfn[tn])
        {
            tarjan(tn);
            low[x]=min(low[x],low[tn]);
            if(dfn[x]==low[tn])
            {
                ++num;
                for(int j=0;j!=tn;--top)
                {
                    j=s[top];
                    add(num,j);
                    add(j,num);
                    ++w[num];
                }
                add(num,x);
                add(x,num);
                ++w[num];
            }
        }
        else low[x]=min(low[x],dfn[tn]);
    }
}
inline void dfs(int x,int father)
{
    b[x]=x<=n;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(tn==father)continue;
        dfs(tn,x);
        ans+=2ll*w[x]*b[x]*b[tn];
        b[x]+=b[tn];
    }
    ans+=2ll*w[x]*b[x]*(sz-b[x]);
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i)w[i]=-1;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        x=read();y=read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    num=n;
    for(int i=1;i<=n;++i)
        if(!dfn[i])
        {
            sz=0;
            tarjan(i);--top;
            dfs(i,0);
        }
    printf("%lld\n",ans);
    return 0;
}

View Code

luogu 3225 矿场搭建 
点双连通分量 其实也是割点的裸题 很有意思。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<vector>
#include<ctime>
#define INF 2147483646
#define ll long long
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(int x)
{
    x<0?putchar('-'),x=-x:0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('\n');return;
}
const int MAXN=502;
int n,len,num,root,c,cnt,sum,m,w;
ll ans;
int low[MAXN],dfn[MAXN],cut[MAXN],vis[MAXN];
int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(dfn[tn]){low[x]=min(low[x],dfn[tn]);continue;}
        else
        {
            tarjan(tn);
            low[x]=min(low[x],low[tn]);
            if(dfn[x]==low[tn])
            {
                ++flag;
                if(flag>1||x!=root)cut[x]=1;
            }
        }
    }
}
void dfs(int x)
{
    vis[x]=cnt;++sum;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(cut[tn]&&vis[tn]!=cnt)
        {
            vis[tn]=cnt;
            ++c;
        }
        if(!vis[tn]&&!cut[tn])dfs(tn);
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    for(int T=1;;++T)
    {
        n=read();
        if(!n)break;
        memset(cut,0,sizeof(cut));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(lin,0,sizeof(lin));
        memset(vis,0,sizeof(vis));
        len=0;num=0;cnt=0;ans=1;m=0;w=0;
        for(int i=1;i<=n;++i)
        {
            int x,y;
            x=read();y=read();
            m=max(m,max(x,y));
            add(x,y);add(y,x);
        }
        for(int i=1;i<=m;++i)if(!dfn[i])root=i,tarjan(i);
        for(int i=1;i<=m;++i)
        {
            if(vis[i]||cut[i])continue;
            ++cnt;sum=0;c=0;
            dfs(i);
            if(!c)ans=ans*(sum-1)*sum/2,w+=2;
            if(c==1)ans*=sum,w+=1;
            if(c==2);
        }
        printf("Case %d: %d %lld\n",T,w,ans);
    }
    return 0;
}

View Code

bzoj 3495 2-sat模型 需要前缀和优化建图 很有意思。

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cctype>
#include<utility>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<deque>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<stack>
#include<string>
#include<cstring>
#define INF 1000000000
#define ll long long
#define mod 1000000007
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=1000010,maxn=MAXN<<3;
int n,m,k,len,cnt,top,num,flag;
int c[MAXN<<2];
int lin[maxn],ver[maxn],nex[maxn];
int s[MAXN<<2],dfn[MAXN<<2],low[MAXN<<2],vis[MAXN<<2];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s[++top]=x;vis[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(!dfn[tn])
        {
            tarjan(tn);
            low[x]=min(low[x],low[tn]);
        }
        else if(vis[tn])low[x]=min(low[x],dfn[tn]);
    }
    if(dfn[x]==low[x])
    {
        ++num;int y;
        do
        {
            y=s[top--];
            vis[y]=0;c[y]=num;
        }
        while(x!=y);
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();k=read();
    for(int i=1;i<=m;++i)
    {
        int x,y;
        x=read();y=read();//x选 x+n不选
        add(x+n,y);add(y+n,x);
    }
    for(int i=1;i<=k;++i)
    {
        int w;
        w=read();
        for(int j=1;j<=w;++j)s[j]=read();
        for(int j=2;j<=w;++j)add(s[j]+2*n,s[j-1]+2*n);//前缀和
        for(int j=w-1;j>=1;--j)add(s[j]+3*n,s[j+1]+3*n);//后缀和
        for(int j=1;j<=w;++j)
        {
            if(j>1)add(s[j],s[j-1]+2*n);
            if(j<w)add(s[j],s[j+1]+3*n);
        }
    }
    for(int i=1;i<=n;++i)add(i+2*n,i+n),add(i+3*n,i+n);
    for(int i=1;i<=4*n;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)if(c[i]==c[i+n])flag=1;
    if(flag)puts("NIE");else puts("TAK");
    return 0;
}

View Code