Posted on 2010-07-24 22:29
Uriel 閱讀(477)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
圖論
題意依舊糾結(jié)，建圖依舊糾結(jié)。。
求含結(jié)點數(shù)>=2的連通分量數(shù)。。
PS：難得有圖論題搜不到DY大牛的解題報告~
用這題來試了各種求強(qiáng)連通分量的模板(今天兩題都用來試模板，然后狂刷。。)
結(jié)果如下：
Kosaraju：G++(加讀入輸出優(yōu)化)：172Ms
Tarjan：C++(不加讀入輸出優(yōu)化)：204Ms
G++(不加讀入輸出優(yōu)化)：250Ms
G++(加讀入輸出優(yōu)化)：94Ms
Tarjan+Disjoint Sets：G++(加讀入輸出優(yōu)化)：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; //邊數(shù)，頂點數(shù)
int flag; //連通分量數(shù)
int link[MAXN]; //標(biāo)色數(shù)組
int size[MAXN]; //每個連通分量包含的頂點數(shù)
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;
}