VIJOS-P1321 魔塔
Time Limit: 1 Sec Memory Limit: 128 MB
Description
在魔塔中有N个房间和M条道路，每条道路上有一个怪，它可以被一种特殊的武器消灭，而每个房间中也存在一种武器。现在知道第I个房间中的武器编号为I，小明（主人翁）初始在J房间，小明想知道哪些房间是他可以去的。
Input
第一行是N，J，M 接下来M行每行三个数Ai，Bi，Ci，分别代表Ai房间和Bi房间之间有路，且此处的怪物可以被Ci号武器消灭。
Output
N行，如果I个房间可以到达，则在第I行输出Yes,否则输出No
Sample Input
6 4 6
1 2 1
1 3 2
2 4 4
3 4 4
3 5 3
5 6 6
Sample Output
1:Yes
2:Yes
3:Yes
4:Yes
5:Yes
6:No
HINT
数据范围 1< =m< =50000,1< =a,b,J< =n< =50000 提示：m,n< 50000不等于说数组可以只开到50000；输出前面无空格
Source
中文题我为什么要告诉你题意？好的，题意就是这样。
现在我要说题解！
首先wyf写了一个暴力，90分，我贴一下他的博客，说不定他写了呢~http://blog.csdn.net/wyfcyx_forever
然后我要说我的正解了。
思想：
每次将能走的点跑一遍确定能开的边，这样就拓展了能走的点，重复操作以得出答案。
实现：
就是先把每个节点用链表挂上其能开的边，然后维护并查集和树构还有一个栈。
并查集：一个点的父亲节点，用于判断连通（/与起点连通）
树构：一棵有向树，每次搜索时从树根扫，然后就可以O（节点数）扫过全部点，把能新开的边计入。
栈：每次当有新开的边将某并查集与起点连通时，把此并查集（树构）的根节点入栈。
具体实现可以参考代码，有新鲜出炉的注释。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50500
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
int u,v,next;
}e[N],ke[N<<1];
int head[N],key[N],cnt,cdk;
void add(int u,int v)
{/*树构*/
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void open(int u,int v,int ky)
{/*给每个点挂上能开的边*/
cdk++;
ke[cdk].u=u;
ke[cdk].v=v;
ke[cdk].next=key[ky];
key[ky]=cdk;
}
int f[N];/*并查集*/
int find(int x)
{
if(x==f[x])return x;
return f[x]=find(f[x]);
}
int n,m,s;
int stk[N],top;/*栈*/
bool visit[N];
void dfs(int x)
{
visit[x]=1;
int i,u,v;
int fa,fb;
for(i=key[x];i;i=ke[i].next)
{/*把x节点能开的边（门）都打开*/
fa=find(ke[i].u);
fb=find(ke[i].v);
if(fa==fb)continue;/*额，你懂得*/
if(fa==s)stk[++top]=fb,f[fb]=s;
else if(fb==s)stk[++top]=fa,f[fa]=s;
/*
某节点被连到了起点，表示能走，
那么就需要处理这个并查集中所有的节点，
把它们能开的边（门）都打开，
这时我们就需要
1. 一个树构来实现高速遍历
2. 一个链表来实现查找边。
*/
else
{/*额，没关系的就自己弄个树构先存着吧*/
add(fa,fb);
f[fb]=fa;
}
}
if(x!=s)for(i=head[x];i;i=e[i].next)
{/*遍历树构中其它点*/
v=e[i].v;
dfs(v);
}
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
int a,b,c;
int u,v,t;
scanf("%d%d%d",&n,&s,&m);
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
open(a,b,c);
}
stk[++top]=s;
while(top){dfs(stk[top--]);}
/*
栈中是从起点这个树根能遍历到的一些枝杈，
它们本身也是一颗颗树
而遍历过程中会有新的边变成可行，
这样就会不停地加进来新的点/点集，
或者说是树。
而!top时遍历也就停止了，
额，没看懂的话不妨手调。
*/
for(i=1;i<=n;i++)
{
printf("%d:",i);
if(visit[i])puts("Yes");
else puts("No");
}
return 0;
}