Uriel's Corner

        最近在做圖論，并且打算暑假軍訓(xùn)之前(再次抱怨學(xué)校大二升大三暑假集訓(xùn)的制度...)除了每周5場組隊(duì)賽之外大部分時(shí)間用來看圖論，雖然也不知道來不來得及。。。
        強(qiáng)連通的問題看了好幾天，因?yàn)榻M隊(duì)賽占用很多時(shí)間，所以相關(guān)題也沒做多少，依然覺得建圖很困難。。

        這題題意繞人。。轉(zhuǎn)述某大牛Blog的解釋：2*N 個(gè)頂點(diǎn)的2 分圖，并且給了一個(gè)完美匹配(Perfect Matching)以及每個(gè)頂點(diǎn)可以連接的其他的頂點(diǎn)。題目要求是否可以確定某 2 個(gè)頂點(diǎn)連邊后，其他 2*(N - 1) 個(gè)頂點(diǎn)的 2 分圖是否可以構(gòu)成完美匹配

        膜拜DY大牛Blog里的解釋，還是不怎么明白，自己畫圖之后感覺是如果是在一個(gè)強(qiáng)連通分量中的話這個(gè)兒子選另外的女生的話原本跟他配對(duì)的女生可以找到另外的男生，所以題目轉(zhuǎn)化為對(duì)每個(gè)兒子求跟他在同一個(gè)連通分量中的女生有哪些，按編號(hào)升序輸出

       這題之前做過3題強(qiáng)連通分量的題，都是用Kosaraju寫的，這題嘗試了一下Tarjan+并查集(基本是照著解題報(bào)告敲的。。)。。
       對(duì)比一下時(shí)間：
       Kosaraju：G++(不加讀入輸出優(yōu)化)：11516Ms
                         G++(加讀入輸出優(yōu)化)：2172Ms
       Tarjan+Disjoint Sets：C++(不加讀入輸出優(yōu)化)：3750Ms
                                          C++(加讀入輸出優(yōu)化)：4579Ms
                                          G++(不加讀入輸出優(yōu)化)：10125Ms
                                          G++(加讀入優(yōu)化)：8579Ms
                                          G++(加讀入輸出優(yōu)化)：500Ms

下面貼下很挫的代碼：
Version：Kosaraju

//Problem: 1904  User: Uriel 
//Memory: 3660K  Time: 2172MS 
//Language: G++  Result: Accepted 
//Version [vector & Kosaraju]
//2010.07.24
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 5010*2

int v,m;
int flag;
int link[MAXN];
int out[MAXN];
int size[MAXN];
int order[MAXN];
int num;
int res[MAXN],nres;
bool vis[MAXN];
vector<int>adja[MAXN];
vector<int>adjb[MAXN];

int in(){
    char ch;
    int a=0;
    while((ch=getchar())==' ' || ch=='\n');
    a*=10;
    a+=ch-'0';
    while((ch=getchar())!=' ' && ch!='\n'){
        a*=10;a+=ch-'0';
    }
    return a;
}

void Out(int a){
    if(a>=10)Out(a/10);
    putchar(a%10+'0');
}

void DFS1(int x){
    vis[x]=true;
    for(int i=0;i<adja[x].size();i++)
        if(!vis[adja[x][i]])DFS1(adja[x][i]);
    order[++num]=x;
}

void DFS2(int x){
    vis[x]=true;
    link[x]=flag;
    size[flag]++;
    for(int i=0;i<adjb[x].size();i++)
        if(!vis[adjb[x][i]])DFS2(adjb[x][i]);
}

void Kosaraju(){
    int i;
    memset(vis,0,sizeof(vis));
    num=0;
    for(i=1;i<=v;i++)
        if(!vis[i])DFS1(i);
    memset(vis,0,sizeof(vis));
    memset(size,0,sizeof(size));
    flag=0;
    for(i=num;i>=1;i--){
        if(!vis[order[i]]){
            flag++;
            DFS2(order[i]);
        }
    }
}

int main()
{
    int x,i,j;
    v=in();
    for(i=1;i<=v;i++){
        m=in();
        for(j=0;j<m;j++){
            x=in();
            adja[i].push_back(x+v);
            adjb[x+v].push_back(i);
        }
    }
    for(j=1;j<=v;j++){
        x=in();
        adja[x+v].push_back(j);
        adjb[j].push_back(x+v);
    }
    Kosaraju();
    for(i=1;i<=v;i++){
        nres=0;
        for(j=0;j<adja[i].size();j++){
            if(link[i]==link[adja[i][j]])res[nres++]=adja[i][j]-v;
        }
        sort(res,res+nres);
        Out(nres);
        for(j=0;j<nres;j++){
            putchar(' ');
            Out(res[j]);
        }
        putchar('\n');
    }
    return 0;
}

Version：Tarjan+disjoint sets

//Problem: 1904  User: Uriel 
//Memory: 3044K  Time: 610MS 
//Language: G++  Result: Accepted 
//Version [Tarjan+disjoint sets]
//2010.07.24
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;

struct node{
    int x,y,next;
};

int e,n,res;
int head[5000],co[5000],father[5000],link[5000],order[5000];
node p[1000000];

int in(){
    char ch;
    int a=0;
    while((ch=getchar())==' ' || ch=='\n');
    a*=10;
    a+=ch-'0';
    while((ch=getchar())!=' ' && ch!='\n'){
        a*=10;a+=ch-'0';
    }
    return a;
}

void out(int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

void addedge(int x,int y){
    p[e].x=x;p[e].y=y;p[e].next=head[x];
    head[x]=e++;
}

void init(){
    int num,x;
    e=0;
    memset(head,-1,sizeof(head));
    memset(link,0,sizeof(link));
    memset(order,0,sizeof(order));
    n=in();
    for(int i=1;i<=n;i++){
        num=in();
        for(int j=1;j<=num;j++){
            x=in();
            addedge(i,x+n);
        }
    }
    for(int i=1;i<=n;i++){
        x=in();
        addedge(x+n,i);
    }
}

int Find(int x){
    if(father[x]==x)return x;
    father[x]=Find(father[x]);
    return father[x];
}

void DFS(int x){
    for(int i=head[x];i!=-1;i=p[i].next){
        if(order[p[i].y]==0){
            order[p[i].y]=order[x]+1;
            DFS(p[i].y);
            if(order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
        }
        else if(co[Find(p[i].y)]==0 && order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
    }
    co[x]=1;
}

void Tarjan(){
    for(int i=1;i<=n+n;i++)father[i]=i;
    for(int i=1;i<=n+n;i++){
        if(order[i]==0){
            order[i]=1;
            DFS(i);
        }
    }
    for(int i=1;i<=n+n;i++)Find(i);
}

int main()
{
    init();
    Tarjan();
    for(int i=1;i<=n;i++){
        res=0;
        for(int j=head[i];j!=-1;j=p[j].next){
            if(father[i]==father[p[j].y])link[res++]=p[j].y-n;
        }
        out(res);
        sort(link,link+res);
        for(int j=0;j<res;j++){
            putchar(' ');
            out(link[j]);        
        }
        puts("");
    }
    return 0;
}

繼續(xù)好好學(xué)圖論。。繼續(xù)膜拜DY大牛Blog。。