也许你能写出一段精致的文字,但你却未必能写出一段精辟的代码。
这是我最近研究连通性问题的一个体验,有的人的书写了好几页纸,可是最终能用的却只有1,2句话而已,我觉得在计算机的世界,没有什么比代码更能直接地表达出这个算法的本质了!所以我以后要多读代码,少看那些空洞的文字。
言归正传,来看题,这是我写的第一个强连通分量的题目,其实求强连通分量的步骤非常简单,正反两次使用dfs,就能得到联通分量的一切信息。做完题目我发现,其实求联通分量最大的作用倒在于,联通分量可以缩成一点,考虑为一个整体,这样可以简化构图,发掘出各个强连通分量外部之间的规律。
解题的方法就是:找出图中所有的强连通分量并将他们缩成一点,再用外部的边重新建图,统计出新图中出度为0的点,如果只有一个,那么说明这个强连通分量中的所有点就是题目要求的点。
题目中要特别注意:内存池中预开的点必须是边的三倍大小,因为构建正图,反图和新图都需要新建节点。(因为这个我wa了一次)
还有就是绝对不要使用vector,我用vector写了一个程序,跑了600+MS,用链表.....47MS......10倍以上的差距,汗 - -!
#include<iostream>
using namespace std;
#define DOTMAX 10001
#define EDGEMAX 50001
struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int t;
node *next;
}dotset[EDGEMAX*3];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int count=0;//每一个case后,count置为0
node *Newnode()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
node *p;
p=&dotset[count];
count++;
return p;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Addnode(node hash[],int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
node *p=&hash[a];
node *q=Newnode();
q->t=b;
q->next=p->next;
p->next=q;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
node hash[DOTMAX];
node nhash[DOTMAX];
node New[DOTMAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gcc;
int order[DOTMAX];
int num;
int id[DOTMAX];
int visit[DOTMAX];
int gccnum[DOTMAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init(node hash[],int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
count=0;
int i;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
hash[i].t=-1;
hash[i].next=NULL;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m;
void dfs(int u)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
visit[u]=1;
node *p;
int v;
for(p=hash[u].next;p!=NULL;p=p->next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
v=p->t;
if(!visit[v])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dfs(v);
}
}
num++;
order[num]=u;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void ndfs(int u)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
visit[u]=1;
id[u]=gcc;
node *p;
int v;
for(p=nhash[u].next;p!=NULL;p=p->next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
v=p->t;
if(!visit[v])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ndfs(v);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](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)
{
int a,b,i;
while(scanf("%d%d",&n,&m)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
init(hash,n);
init(nhash,n);
init(New,n);
for(i=1;i<=m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf("%d%d",&a,&b);
Addnode(hash,a,b);
Addnode(nhash,b,a);
}
memset(visit,0,sizeof(visit));
num=0;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!visit[i])
dfs(i);
}
memset(visit,0,sizeof(visit));
gcc=0;
for(i=num;i>=1;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(!visit[order[i]])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
gcc++;
ndfs(order[i]);
}
}
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
node *p;
for(p=hash[i].next;p!=NULL;p=p->next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(id[i]!=id[p->t])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Addnode(New,id[i],id[p->t]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
int cnt=0;
memset(gccnum,0,sizeof(gccnum));
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
gccnum[id[i]]++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mark=0;
for(i=1;i<=gcc;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(New[i].next==NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cnt++;
mark=i;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(cnt==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n",gccnum[mark]);
}
else
printf("%d\n",0);
}
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)