NOIp 2015信息传递【tarjan/拓扑/并查集】

一道好的NOIp题目，在赛场上总能用许多算法A掉。比如这道和关押罪犯。

法一：tarjan在有向图中跑最小环

有人从别人口中得知自己信息，等效于出现了一个环。于是这就变成了一个有向图tarjan强连通分量的板子题。

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #define maxn 200090

 using namespace std;

 int n,y,tot,ans=,dfs_clock,scc_cnt,tong[maxn],dfn[maxn],low[maxn],head[maxn],scc[maxn];

 stack<int>s;

 struct node{

     int to,next;

 }edge[maxn];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void dfs(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             dfs(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==p) break;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

      scanf("%d",&y),add(i,y);

     for(int i=;i<=n;i++)

     {

         if(!dfn[i]) dfs(i);

         tong[scc[i]]++;

     }

     for(int i=;i<=scc_cnt;i++) if(tong[i]>&&tong[i]<ans) ans=tong[i];

     printf("%d\n",ans);

     return ;

 }

法二：拓扑排序

图中可能会出现很多环，求最小的一个。我们跑一遍拓扑排序后，那些不曾入到队列中的点就是成环的点。于是我们可以边拓扑排序边标记最后找到那些在环上的点，从他们出发分别求出环的大小进行比较。

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int n,x,ans=,cnt,tot;

 int du[],head[],vis[],flag[];

 struct node{

     int to,next;

 }edge[];

 queue<int>q;

 void add(int x,int y)

 {

     edge[++tot].next=head[x];

     edge[tot].to=y;

     head[x]=tot;

 }

 void topo()

 {

     for(int i=;i<=n;i++)

         if(!du[i]) q.push(i),flag[i]=;

     while(!q.empty())

     {

         int u=q.front();q.pop();

         for(int i=head[u];i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(--du[v]==) q.push(v),flag[v]=;

         }

     }

 }

 void dfs(int x)

 {

     vis[x]=,cnt++;

     for(int i=head[x];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(vis[y]) return ;

         dfs(y);

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d",&x),add(i,x),du[x]++;

     topo();

     for(int i=;i<=n;i++)

         if((!flag[i])&&(!vis[i]))

         {

             cnt=;

             dfs(i);

             ans=min(ans,cnt);

         }

     printf("%d",ans);

     return ;

 }

法三：并查集

https://anyway.blog.luogu.org/solution-p2661

巴特西

NOIp 2015信息传递【tarjan/拓扑/并查集】

最新文章

热门文章