主题材料叙述 Description, 会集论与图论对于小松来说是比数字逻辑轻巧

分拣标签 Tags 点此举行

 

标准的话标题已经已经说得很明白了,便是x,y,z之间的关联,而xyz又正好是四个字母,这样大家用Flyod就足以全面化解了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=1001;
 6 const int maxn=0x7fffffff;
 7 int map[MAXN][MAXN];
 8 int vis[100001];
 9 int x,y,z;
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         memset(map,0,sizeof(map));
17         int n,m;
18         scanf("%d%d",&n,&m);
19         /*for(int i=1;i<=n;i++)
20         for(int j=1;j<=n;j++)
21             map[i][j]=maxn;
22         for(int i=1;i<=n;i++)
23         map[i][i]=0;*/
24         for(int i=1;i<=m;i++)
25         {
26             scanf("%d%d",&x,&y);
27             map[x][y]=1;
28         }
29         int flag=0;
30         for(int x=1;x<=n;x++)
31         {
32             for(int y=1;y<=n;y++)
33             {
34                 if(map[x][y]==1)
35                 for(int z=1;z<=n;z++)
36                 {
37                     /*if(map[i][j]||(map[i][k]&&map[k][j]))
38                     vis[i]=vis[j]=1;*/
39                     if(map[y][z]==1)
40                     {
41                         if(map[x][z]==0)
42                         {
43                             flag=1;
44                             break;
45                         }
46                     }
47                 }
48             }
49         }
50         /*for(int i=1;i<=n;i++)
51         {
52             if(vis[i]==0)
53             {
54                 flag=1;
55                 break;
56             }
57         }*/
58         if(flag==1)
59         {
60             printf("No\n");
61         }
62         else
63         {
64             printf("Yes\n");
65         }
66     }
67     return 0;
68 }

 

101玖 群集论与图论

ca88亚洲城网站, 

时限: 1 s

空间范围: 12七千 KB

标题品级 : 黄金 Gold

 

 

 

标题叙述 Description

     
 集合论与图论对于小松来说是比数字逻辑轻易,比数据结构难的1门职业必修课。即使小松在高级中学的时候曾经自学过了离散数学中的图论,组合,群论等文化。但对此集结论,小松依然比较面生的。集结论的众多事物也事关到了图论的学识。

 

       在第肆讲的就学中,小松学到了“有序对”这么一个定义,即用<x,
y>表示有序对x和y。要留意的是不改变对<x, y>不对等有序对<y,
x>。对于多个稳步对集结Wrangler={<x,y>, <y, z>, <x,
 z>,……},大家说奥迪Q5是传递的,当且仅当她满足上面包车型大巴习性:

 

浅莲灰字体用直观的言语描述是:若是存在<x, y>∈猎豹CS6,<y,
z>∈Rubicon,那么自然存在<x, z>∈奇骏。

 

       那里集结奥德赛可以对应到三个有向图G,有序对<x
,y>对应到了G中的一条有向边。
你今后的任务是,对于自由给定的二个粗略有向图G(同一有向边不出现三回),判定G是还是不是持有传递性。

 

ca88亚洲城网站 1

输入描述 Input Description

     
 输入文件set.in第三行蕴含测试数据的个数T(壹<=T<=十)。接下来T组测试数据,每组测试数据第2行包罗多个个整数n和m(一<=n<=一千,
n<=m<=一千00),表示G申月素个数和有向边的个数,接下去的m行每行一个整数x,
y(一<=x,y<=n)表示x与y之间有一条有向边连接。

出口描述 Output Description

     
 对于每组数据,假若G是传递的,你要求向输出文件set.out输出壹行”Yes”,
不然输出壹行”No”。

样例输入 Sample Input

2

3 3

1 2

1 3

2 3

4 5

1 2

1 3

1 4

2 3

3 4

样例输出 Sample Output

Yes

No

数码范围及提醒 Data Size & Hint

有30%满足1<=n<=100, 1<=m<=10000;

有百分之百的数目知足一<=n<=1000, 一<=m<=一千00;

 1 #include <cstdio>
 2 #include <cstring>
 3 bool graph[1001][1001];
 4 int main() 
 5 {
 6     int t,n,m,a,b;
 7     bool trans = true;
 8     scanf("%d",&t);
 9     for(int i = 0; i < t; i++) 
10     {
11         trans = true;
12         scanf("%d%d",&n,&m);
13         memset(graph,0,sizeof(graph));
14         for(int j = 0; j < m; j++) 
15         {
16             scanf("%d%d",&a,&b);
17             graph[a][b] = true;
18         }
19         for(int x = 1; x <= n; x++)
20             for(int y = 1; y <= n; y++)
21                 if(graph[x][y] && x!=y)
22                     for(int z = 1; z <= n; z++)
23                         if(graph[y][z])
24                             if(!graph[x][z]) 
25                             {
26                                 trans = false;
27                                 break;
28                             }
29         if(trans)printf("Yes\n");
30         else printf("No\n");
31     }
32     return 0;
33 }

 

十1九 集合论与图论

 

 时限: 一s

 空间限制: 127000KB

 标题等第 : 黄金
戈尔德

题解

 查看运维结果

 

 

主题素材叙述 Description

     
 集结论与图论对于小松来说是比数字逻辑轻便,比数据结构难的一门职业必修课。尽管小松在高级中学的时候曾经自学过了离散数学中的图论,组合,群论等学问。但对于集结论,小松依旧相比目生的。集结论的大多东西也关系到了图论的学问。

 

       在第6讲的上学中,小松学到了“有序对”这么三个定义,即用<x,
y>表示有序对x和y。要专注的是铁钉铁铆对<x, y>不对等有序对<y,
x>。对于二个一如既往对集结陆风X8={<x,y>, <y, z>, <x,
 z>,……},大家说凯雷德是传递的,当且仅当她满意下边包车型地铁品质:

 

莲灰字体用直观的言语描述是:假使存在<x, y>∈卡宴,<y,
z>∈猎豹CS陆,那么自然存在<x, z>∈中华V。

 

       这里集结途睿欧能够对应到一个有向图G,有序对<x
,y>对应到了G中的一条有向边。
你未来的任务是,对于自由给定的贰个简单易行有向图G(同壹有向边不出现一遍),判定G是不是持有传递性。

 

ca88亚洲城网站 2

输入描述 Input Description

     
 输入文件set.in第2行李包裹括测试数据的个数T(一<=T<=十)。接下来T组测试数据,每组测试数据第三行李包裹括八个个整数n和m(一<=n<=一千,
n<=m<=一千00),表示G十月素个数和有向边的个数,接下去的m行每行二个整数x,
y(一<=x,y<=n)表示x与y之间有一条有向边连接。

出口描述 Output Description

     
 对于每组数据,即便G是传递的,你要求向输出文件set.out输出一行”Yes”,
不然输出1行”No”。

样例输入 Sample Input

2

3 3

1 2

1 3

2 3

4 5

1 2

1 3

1 4

2 3

3 4

样例输出 Sample Output

Yes

No

多少范围及提醒 Data Size & Hint

有30%满足1<=n<=100, 1<=m<=10000;

有百分百的数码满意1<=n<=1000, 壹<=m<=100000;

 

 

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
typedef struct edge{
    int to;
    int next;
}E;
int head[100000];
E a[100000];
int dfs(int begin,int num)
{
    int temp;
    int lemp;
    int flag=0;
    temp=head[num];
    lemp=head[begin];
    while(temp)
    {
        flag=0;
        while(lemp)
        {
            if(a[lemp].to==a[temp].to)
            {
                flag=1;
                break;
            }
            lemp=a[lemp].next;
        }
        if(flag==0)
         return 0;
        temp=a[temp].next;
    }
    return 1;
}
int main()
{
    int T;
    int N,M;
    int i;
    int u,v,temp;
    int flag=1;
    scanf("%d",&T);
    while(T--)
    {   
        flag=1;
        scanf("%d %d",&N,&M);
        memset(head,0,sizeof(head));
        for(i=1;i<=100000;i++)//要手动置零 
        {
            a[i].to=0;
            a[i].next=0;
        }
        for(i=1;i<=M;i++)
        {
            scanf("%d %d",&u,&v);
            a[i].to=v;
            a[i].next=head[u];
            head[u]=i;
        }
        for(i=1;i<=N;i++)
        {
            temp=head[i];
            while(temp)
            {
                if(dfs(i,a[temp].to))
                 temp=a[temp].next;
                else
                {
                    flag=0;
                    break;
                }
            }
            if(flag==0)
            break;
        }
        if(flag)
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

 

十1九 会集论与图论

 

时限: 一 s

空间范围: 128000 KB

题目等第 : 黄金 戈尔德

 

 

 

 

难点叙述 Description

     
 会集论与图论对于小松来讲是比数字逻辑轻巧,比数据结构难的1门专门的学业必修课。固然小松在高级中学的时候已经自学过了离散数学中的图论,组合,群论等知识。但对此集合论,小松照旧相比目生的。集合论的大多事物也涉嫌到了图论的学问。

 

       在第六讲的学习中,小松学到了“有序对”这么三个概念,即用<x,
y>表示有序对x和y。要小心的是平稳对<x, y>不等于有序对<y,
x>。对于3个萧规曹随对集合奇骏={<x,y>, <y, z>, <x,
 z>,……},大家说奥迪Q3是传递的,当且仅当他满意下边的特性:

 

新民主主义革命字体用直观的语言讲述是:要是存在<x, y>∈Evoque,<y,
z>∈HummerH贰,那么必然存在<x, z>∈ENCORE。

 

       那里群集Highlander能够对应到二个有向图G,有序对<x
,y>对应到了G中的一条有向边。
你今后的天职是,对于随便给定的三个简短有向图G(同一有向边不出新两回),判定G是还是不是富有传递性。

 

ca88亚洲城网站 3

输入描述 Input Description

     
 输入文件set.in第一行李包裹括测试数据的个数T(壹<=T<=十)。接下来T组测试数据,每组测试数据第三行包括五个个整数n和m(一<=n<=一千,
n<=m<=一千00),表示G中元素个数和有向边的个数,接下去的m行每行3个整数x,
y(一<=x,y<=n)表示x与y之间有一条有向边连接。

输出描述 Output Description

     
 对于每组数据,倘使G是传递的,你必要向输出文件set.out输出一行”Yes”,
不然输出1行”No”。

样例输入 Sample Input

2

3 3

1 2

1 3

2 3

4 5

1 2

1 3

1 4

2 3

3 4

样例输出 Sample Output

Yes

No

数量范围及提醒 Data Size & Hint

有30%满足1<=n<=100, 1<=m<=10000;

有百分之百的数量满意一<=n<=一千, 1<=m<=100000;

相关文章