absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-2] Vijos 1951
[破碎的状态] [-1] (Failed)Splay BZOJ 1056

[破碎的状态] [-2] POJ 3693

absi2011 posted @ Jul 20, 2016 10:50:29 PM in 刷题记录 with tags SCC 拓扑排序 POJ 小高考 , 839 阅读

感谢@JCarlson 为我找题&翻译

求一个图是否任意两点i,j都可以到达(从i到j或从j到i)

解法:

scc缩环,然后拓扑排序判定是否是唯一的拓扑序列

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
};
edge * li[1005];
edge * li2[1005];
int top=0;
edge * new_edge()
{
    static edge a[100005];
    return &a[top++];
}
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge_2(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li2[x];
    li2[x]=t;
}
int dfn[1005];
int low[1005];
int inque[1005];
int belong_to[1005];
int num;
int newn;
bool flag;
void scc(int x)
{
    static int top=0;
    static int que[1005];
    que[top++]=x;
    inque[x]=true;
    dfn[x]=num++;
    low[x]=dfn[x];
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (dfn[t->y]==-1)
        {
            scc(t->y);
            low[x]=min(low[x],low[t->y]);
        }
        else if (inque[t->y])
        {
            low[x]=min(low[x],dfn[t->y]);
        }
    }
    if (low[x]==dfn[x])
    {
        for (;;)
        {
            top--;
            belong_to[que[top]]=newn;
            inque[que[top]]=false;
            if (que[top]==x) break;
        }
        newn++;
    }
}
int in[1005];
void topo_sort()
{
    int i;
    for (i=0;i<newn;i++)
    {
        edge * t;
        for (t=li2[i];t!=0;t=t->next)
        {
            in[t->y]++;
        }
    }
    static int que[1005];
    int front=0,rail=0;
    for (i=0;i<newn;i++)
    {
        if (in[i]==0) que[rail++]=i;
    }
    for (;front<rail;front++)
    {
        if (rail-front>=2) flag=false;
        edge * t;
        for (t=li2[que[front]];t!=0;t=t->next)
        {
            in[t->y]--;
            if (in[t->y]==0)
            {
                que[rail++]=t->y;
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i;
        memset(li,0,sizeof(li));
        memset(li2,0,sizeof(li2));
        top=0;
        num=0;
        newn=0;
        for (i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            insert_edge(x,y);
        }
        memset(dfn,-1,sizeof(dfn));
        for (i=0;i<n;i++)
        {
            if (dfn[i]==-1) scc(i);
        }
        for (i=0;i<n;i++)
        {
            edge * t;
            for (t=li[i];t!=0;t=t->next)
            {
                if (belong_to[i]==belong_to[t->y]) continue;
                insert_edge_2(belong_to[i],belong_to[t->y]);
            }
        }
        flag=true;
        topo_sort();
        if (flag)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}
AP 2nd Inter Economi 说:
Sep 08, 2022 10:17:11 PM

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 2nd Inter Economics Question Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper. The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter