|
Posted on 2010-07-24 22:29 Uriel 阅读(470) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 图论
题意依旧纠结,建图依旧纠结。。 求含结点数>=2的连通分量数。。 PS:难得有图论题搜不到DY大牛的解题报告~ 用这题来试了各种求强连通分量的模板(今天两题都用来试模板,然后狂刷。。) 结果如下: Kosaraju:G++(加读入输出优化):172Ms Tarjan:C++(不加读入输出优化):204Ms G++(不加读入输出优化):250Ms G++(加读入输出优化):94Ms Tarjan+Disjoint Sets:G++(加读入输出优化):16Ms 暂时Rank 1 求连通分量部分基本是贴代码的,Tarjan的代码感谢光光提供模板~ 代码比较挫。。可以无视。。 Version:Kosaraju
//Problem: 3180 User: Uriel //Memory: 2120K Time: 172MS //Language: G++ Result: Accepted //Version: [Kosaraju] //2010.07.24 #include<vector> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; #define MAXN 10010
int e,v; //边数,顶点数 int flag; //连通分量数 int link[MAXN]; //标色数组 int size[MAXN]; //每个连通分量包含的顶点数 int order[MAXN]; //DFS1序列 int num,res; bool vis[MAXN]; vector<int>adja[MAXN];//正向 vector<int>adjb[MAXN];//逆向
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 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'); }
int main(){ int x,y,i; v=in();e=in(); for(i=0;i<e;i++){ x=in();y=in(); adja[x].push_back(y); adjb[y].push_back(x); } Kosaraju(); res=0; for(i=1;i<=flag;i++){ if(size[i]>=2)res++; } out(res); putchar('\n'); return 0; }
Version:Tarjan
//Problem: 3180 User: Uriel //Memory: 1596K Time: 94MS //Language: G++ Result: Accepted /**/////Version: [Tarjan] ////2010.07.24#include<vector> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std;
#define N 10010
int n,m,res; int dfn[N],low[N],instack[N]; int belong[N],stap[N],cnt[N]; int stop,bcnt,dindex;
vector<int>vec[N];
void Tarjan(int i){ int j; dfn[i]=low[i]=++dindex; instack[i]=true; stap[++stop]=i; vector<int>::iterator it; for(it=vec[i].begin();it!=vec[i].end();it++){ j=*it; if(!dfn[j]){ Tarjan(j); if(low[j]<low[i])low[i]=low[j]; } else if(instack[j] && dfn[j]<low[i])low[i]=dfn[j]; } if(dfn[i]==low[i]){ bcnt++; do{ belong[j=stap[stop--]]=bcnt; cnt[bcnt]++; instack[j]=false;
}while(j!=i); } }
void Sov(){ int i; stop=bcnt=dindex=0; memset(dfn,0,sizeof(dfn)); memset(cnt,0,sizeof(cnt)); for(i=1;i<=n;i++) if(!dfn[i])Tarjan(i); }
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'); }
int main(){ int a,b,i; n=in();m=in(); for(i=0;i<m;i++){ a=in();b=in(); vec[a].push_back(b); } Sov(); res=0; for(i=0;i<=bcnt;i++) if(cnt[i]>=2)res++; out(res); putchar('\n'); return 0; }
Version:Tarjan+Disjoint Sets
//Problem: 3180 User: Uriel //Memory: 1072K Time: 32MS //Language: G++ Result: Accepted //Version: [Tarjan+Tarjan+Disjoint Sets] //2010.07.24 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
struct node{ int y,next; };
int e; int n; //点 int m; //边 int res; int head[10010],co[10010],father[10010],link[10010],order[10010]; node p[50010];
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].y=y;p[e].next=head[x]; head[x]=e++; }
void init(){ int num,x,y; e=0; memset(head,-1,sizeof(head)); memset(link,0,sizeof(link)); memset(order,0,sizeof(order)); n=in(); m=in(); for(int i=1;i<=m;i++){ x=in(); y=in(); addedge(x,y); } }
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;i++)father[i]=i; for(int i=1;i<=n;i++){ if(order[i]==0){ order[i]=1; DFS(i); } } for(int i=1;i<=n;i++)Find(i); }
int main() { init(); Tarjan(); for(int i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=p[j].next){ link[father[i]]++; } } res=0; for(int i=1;i<=n;i++) if(link[i]>=2)res++; printf("%d\n",res); return 0; }
|