| 记录编号 |
127905 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[東方S1] 上白泽慧音 |
最终得分 |
100 |
| 用户昵称 |
 水中音 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.100 s |
| 提交时间 |
2014-10-16 15:54:07 |
内存使用 |
67.77 MiB |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
queue<int> A;
bool pan[5001]={0},pan2[5001]={0},pan3[3001][3001]={0},pan4[5001]={0};
int n,m,i,j,l,p,zj1,zj2,zj3,zj4,zj5;
int fa[5001]={0},twosum=0,onesum=0,two_next[100001]={0},two_to[100001]={0},two_head[5001]={0},one_next[100001]={0},one_to[100001]={0},one_head[5001]={0};
int Set_sum=0,Set_team[3001][5001]={0},Set_return[5001]={0};
void init()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&zj1,&zj2,&zj3);
if(zj3==1)
{
onesum++;
one_to[onesum]=zj2;
one_next[onesum]=one_head[zj1];
one_head[zj1]=onesum;
pan2[zj1]=true;//记录单向路节点
}
else
{
twosum++;
two_to[twosum]=zj2;
two_next[twosum]=two_head[zj1];
two_head[zj1]=twosum;
twosum++;
two_to[twosum]=zj1;
two_next[twosum]=two_head[zj2];
two_head[zj2]=twosum;
pan[zj1]=true;
pan[zj2]=true;//记录双向路节点
}
}
}
void Set_Find()
{
for(i=1;i<=n;i++)
if(pan[i])//寻找标记的双向路节点
{
Set_sum++;//将联通的双向路归为一个集合
pan4[ Set_sum ]=true;
A.push(i);pan[i]=false;
while(!A.empty())
{
j=A.front();A.pop();fa[j]=i;//取消标记代表已经访问过
Set_team[ Set_sum ][0]++;
Set_team[ Set_sum ][ Set_team[ Set_sum ][0] ]=j;//接入集合
for(j=two_head[j];j;j=two_next[j])
if(pan[ two_to[j] ])
{
pan[ two_to[j] ]=false;
fa[ two_to[j] ]=i;
A.push( two_to[j] );
}
}
Set_return[i]=Set_sum;
}
for(i=1;i<=n;i++)
if(pan2[i]&&(!fa[i]))//单向路结点假如不存在父亲则自身为一个集合
{
Set_sum++;
pan4[ Set_sum ]=true;
Set_team[ Set_sum ][0]=1;
Set_team[ Set_sum ][1]=i;
fa[i]=i;
Set_return[i]=Set_sum;
}
}
void FromYtoY()
{
for(i=1;i<=Set_sum;i++)
{
zj2=Set_team[i][1];
for(j=one_head[zj2];j;j=one_next[j])
{
zj1=one_to[j];
while(zj1!=fa[zj1])zj1=fa[zj1];
zj1=Set_return[zj1];
one_to[j]=zj1;
//将集合中根节点单向路所指结点设置为所指结点对应集合的根节点的集合编号
}
for(p=2;p<=Set_team[i][0];p++)
{
j=Set_team[i][p];
for(j=one_head[j];j;j=one_next[j])
{
onesum++;
one_next[onesum]=one_head[zj2];
one_head[zj2]=onesum;
zj1=one_to[j];
while(zj1!=fa[zj1]) zj1=fa[zj1];
zj1=Set_return[zj1];
one_to[onesum]=zj1;
//将集合中所有元素的单向路所指结点转为所指结点根节点并赋给该集合根节点
}
}
}
for(i=1;i<=Set_sum;i++)
{
A.push(i);
while(!A.empty())
{//寻找集合间的单向路，并用bool型记录
j=A.front();A.pop();
j=Set_team[j][1];
for(j=one_head[j];j;j=one_next[j])
if(!pan3[i][ one_to[j] ])
{
pan3[i][ one_to[j] ]=true;
A.push( one_to[j] );
}
}
}
}
void End_find()
{
for(i=1;i<=Set_sum;i++)
{
pan4[i]=false;
for(p=i+1;p<=Set_sum;p++)
if(pan3[i][p]&&pan3[p][i]&&pan4[p])
{//合并有双向路的集合
pan4[p]=false;
for(j=1;j<=Set_team[p][0];j++)
{
Set_team[i][0]++;
Set_team[i][ Set_team[i][0] ]=Set_team[p][j];
}
}
}
zj1=0;
for(i=1;i<=Set_sum;i++)//寻找元素最多者
{
if(zj1<Set_team[i][0])
{
zj1=Set_team[i][0];
zj2=i;
}
if(zj1==Set_team[i][0])//寻找字典序最小者
{
sort(Set_team[zj2]+1,Set_team[zj2]+(Set_team[zj2][0]+1));
sort(Set_team[i]+1,Set_team[i]+(Set_team[i][0]+1));
zj3=1;
while(zj3<=zj1&&Set_team[zj2][zj3]==Set_team[i][zj3]) zj3++;
if(Set_team[zj2][zj3]>Set_team[i][zj3]) zj2=i;
}
}
sort(Set_team[zj2]+1,Set_team[zj2]+(Set_team[zj2][0]+1));//按字典序排序
}
int main()
{
freopen("classroom.in","r",stdin);
freopen("classroom.out","w",stdout);
init();
Set_Find();
FromYtoY();
End_find();
printf("%d\n",Set_team[zj2][0]);
for(i=1;i<Set_team[zj2][0];i++)
printf("%d ",Set_team[zj2][i]);
printf("%d\n",Set_team[zj2][i]);
return 0;
}