Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:TTTTTTTTTTTTTTTTT了,2333333333333333333333

Posted by zhangweiwen at 2021-08-10 12:00:19 on Problem 1470
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator