拓扑排序|Tarjan - 传话 「CODEVS1506」
题目描述
[问题描述]
兴趣小组的同学来自各个学校,为了增加友谊,晚会上又进行了一个传话游戏,如果a认识b,那么a收到某个消息,就会把这个消息传给b,以及所有a认识的人。
如果a认识b,b不一定认识a。
所有人从1到n编号,给出所有“认识”关系,问如果i发布一条新消息,那么会不会经过若干次传话后,这个消息传回给了i,1<=i<=n。
[输入文件]
输入文件message.in中的第一行是两个数n(n<1000)和m(m<10000),两数之间有一个空格,表示人数和认识关系数。
接下来的m行,每行两个数a和b,表示a认识b。1<=a, b<=n。认识关系可能会重复给出,但一行的两个数不会相同。
[输出文件]
输出文件message.out中一共有n行,每行一个字符T或F。第i行如果是T,表示i发出一条新消息会传回给i;如果是F,表示i发出一条新消息不会传回给i。
[输入样例]
4 6
1 2
2 3
4 1
3 1
1 3
2 3
[输出样例]
T
T
T
F
Analysis
还是太年少清蒸了啊
以为是拓扑排序判环,然后潇潇洒洒写了一发,居然只能过70pts
去网上找标程来对拍,发现拓扑排序会判错很多情况
比如:
代码大概长这样:
#include<bits/stdc++.h>
#define in read()
#define N 10009
#define M 50009
using namespace std;
inline int read(){
int data=0;int w=1; char ch=0;
ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return data*w;
}
int n,m,du[N],chu[N];
int nxt[M],to[M],head[N],ecnt=0;
inline void add(int x,int y){
nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;
}
int main(){
n=in;m=in;
int i,j,a,b;
for(i=1;i<=m;++i){
a=in;b=in;
add(a,b);du[b]++;chu[a]++;
}
queue<int> q;
for(i=1;i<=n;++i)
if(!du[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
--du[v];
if(!du[v]) q.push(v);
}
}
for(i=1;i<=n;++i)
{
if(du[i]&&chu[i]) printf("T\n");
else printf("F\n");
}
return 0;
}
然后思考了一下,发现找的标程根本跑不过10000的数据(n2的,差评。。)
然后就放弃继续思考拓扑了(再想下去可能就要面向数据了)
发现就是要判一个点是否在环上嘛,Tajan随随便便缩点,缩完后判断所在联通块的大小是否大于1,如果是就说明可以传回自己,否则不行
Code
#include<bits/stdc++.h>
#define in read()
#define N 20009
#define M 100009
using namespace std;
inline int read(){
int data=0;int w=1; char ch=0;
ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return data*w;
}
int n,m;
int nxt[M],to[M],head[N],ecnt=0;
inline void add(int x,int y){nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;}
int dfn[N],low[N],be[N],sze[N],dfs=0,num=0;
bool insta[N];
stack<int> S;
inline void tarjan(int u){
S.push(u);insta[u]=1;
dfn[u]=low[u]=++dfs;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[v],low[u]);
}
else if(insta[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
++num;int x;
do{
x=S.top();S.pop();insta[x]=0;
be[x]=num;sze[num]++;
}while(x!=u);
}
}
int main(){
n=in;m=in;
int i,j,a,b;
for(i=1;i<=m;++i){
a=in;b=in;
add(a,b);
}
for(i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(i=1;i<=n;++i){
if(sze[be[i]]>1) printf("T\n");
else printf("F\n");
}
return 0;
}