| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:TTTTTTTTTTTTTTTTT了,2333333333333333333333In Reply To:TTTTTTTTTTTTTTTTT了,2333333333333333333333 Posted by:mywaythere at 2016-10-19 15:04:38 > #include<iostream>
> #include<cstdio>
> #include<vector>
> #include<cstring>
> using namespace std;
> const int mt=1000+5;
> int time[mt];
> struct edgeedge
> {
> int to,next;
> } e[mt*2];
> int head[mt],ind[mt],f[mt],vis[mt];
> vector<int>ques[mt];
> int findf(int a)
> {
> if(f[a]!=a) return f[a]=findf(f[a]);
> return a;
> }
> void uion(int u,int v)
> {
> int f1=findf(u),f2=findf(v);
> if(f1!=f2) f[f2]=f1;
> }
> void tarjan(int s)
> {
> int u=s;
> vis[u]=1,f[u]=u;//2333333333
> int siz=ques[u].size();
> for(int i=0; i<siz; i++)//为什么要先询问,再dfs更新
> if(vis[ques[u][i]]) time[findf(ques[u][i])]++;//cout<<"i"<<i<<" "<<ques[u][i]<<" "<<findf(ques[u][i])<<endl;}
> for(int i=head[u]; i!=-1; i=e[i].next)
> {
> int v=e[i].to;
> if(!vis[v]) tarjan(v),uion(u,v);
> f[u]=u;//233333333
> }
> }
> int c=0;
> void adde(int u,int v)
> {
> e[c].to=v;
> e[c].next=head[u];
> head[u]=c++;
> }
> inline bool get(int &a)
> {
> char c;
> while(((c=getchar())<'0'||c>'9')&&c!=EOF);
> if(c==EOF)return 0;
> for(a=0; c>='0'&&c<='9'; c=getchar())a=a*10+c-'0';
> return 1;
> }
> int main()
> {
> int n,s,t,k;
> while(get(n))
> {
> for(int i=1; i<=n; i++)
> vis[i]=0,head[i]=-1,ind[i]=0,f[i]=i,ques[i].clear(),time[i]=0;
> for(int i=0; i<n; i++)
> {
> //int u,v,t;
> //scanf("%d:(%d)",&u,&t);
> get(s);
> get(k);
> for(int j=0; j<k; j++)
> {
> //scanf("%d",&v);
> get(t);
> adde(s,t),ind[t]++;//为什么是单向边
> }
> }
> //int q;
> //scanf("%d",&q);
> get(k);
> for(int i=1; i<=k; i++)
> {
> /*int u,v;
> scanf(" (%d %d)",&u,&v);
> if(u==v)
> {
> time[u]++; //就当我无聊特判吧
> continue;
> }
> ques[u].push_back(v);
> ques[v].push_back(u);*/
> get(s);
> get(t);
> if(s==t)
> {
> f[s]++;
> continue;
> }
> ques[s].push_back(t);
> ques[t].push_back(s);
> }
> int s=0;
> for(int i=1; i<=n; i++)
> if(ind[i]==0)
> {
> s=i;
> break;
> }
> tarjan(s);
> for(int i=1; i<=n; i++)
> if(time[i]) printf("%d:%d\n",i,time[i]);//我改了半天,结果这里不能加&(这么...的错误)
> }
> return 0;
> }
> 我实在不想去改stl了,TLE的心累啊(QAQ,求助)
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator