|
Posted on 2010-07-24 22:29 Uriel 阅读(473) 评论(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
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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];//逆向
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=num;i>=1;i--) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!vis[order[i]]) {
flag++;
DFS2(order[i]);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int in() {
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while((ch=getchar())!=' ' && ch!='\n') {
a*=10;a+=ch-'0';
}
return a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void out(int a) {
if(a>=10)out(a/10);
putchar(a%10+'0');
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int x,y,i;
v=in();e=in();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=0;i<e;i++) {
x=in();y=in();
adja[x].push_back(y);
adjb[y].push_back(x);
}
Kosaraju();
res=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**/////Version: [Tarjan]
////2010.07.24 #include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define N 10010
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m,res;
int dfn[N],low[N],instack[N];
int belong[N],stap[N],cnt[N];
int stop,bcnt,dindex;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector<int>vec[N];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Tarjan(int i) {
int j;
dfn[i]=low[i]=++dindex;
instack[i]=true;
stap[++stop]=i;
vector<int>::iterator it;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(it=vec[i].begin();it!=vec[i].end();it++) {
j=*it;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(dfn[i]==low[i]) {
bcnt++;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) do {
belong[j=stap[stop--]]=bcnt;
cnt[bcnt]++;
instack[j]=false;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}while(j!=i);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int in() {
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while((ch=getchar())!=' ' && ch!='\n') {
a*=10;a+=ch-'0';
}
return a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void out(int a) {
if(a>=10)out(a/10);
putchar(a%10+'0');
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int a,b,i;
n=in();m=in();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct node {
int y,next;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int e;
int n; //点
int m; //边
int res;
int head[10010],co[10010],father[10010],link[10010],order[10010];
node p[50010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int in() {
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while((ch=getchar())!=' ' && ch!='\n') {
a*=10;a+=ch-'0';
}
return a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void out(int a) {
if(a>=10)out(a/10);
putchar(a%10+'0');
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void addedge(int x,int y) {
p[e].y=y;p[e].next=head[x];
head[x]=e++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=m;i++) {
x=in();
y=in();
addedge(x,y);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Find(int x) {
if(father[x]==x)return x;
father[x]=Find(father[x]);
return father[x];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void DFS(int x) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=head[x];i!=-1;i=p[i].next) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Tarjan() {
for(int i=1;i<=n;i++)father[i]=i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=n;i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(order[i]==0) {
order[i]=1;
DFS(i);
}
}
for(int i=1;i<=n;i++)Find(i);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
init();
Tarjan();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=n;i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
|