ZZUOJ-1199-サイズ関係(トポロジーソート!)

4212 ワード

1199:サイズ関係
Time Limit: 2 Sec
Memory Limit: 128 MB
Submit: 126
Solved: 27
[ Submit][ Status][ Web Board]
Description
大きな関係のセットを知ってから、すべての関係が成立するかどうか、すなわち関係間に矛盾がないかどうかを判断することができます.例えば、AInput
複数のデータのグループです.各データのグループは次のとおりです.
最初の行には数字mがあります.mはmグループ関係(1<=m<=400)を表し、次にm行は行ごとに1つの関係があり、2つの異なるアルファベットと1つの記号で表される.(入力保証アルファベットは「A」-「Z」の間で、関係記号は>,<)のみです.
Output
データ群毎に「YES」または「NO」が出力.
Sample Input

3
A<B
A<C
B<C

3
A<B
B<C
C<A

Sample Output

YES
NO

HINT
Source
鄭州大学第7回ACM大学生プログラム設計コンテスト
最近、データ構造は図論のトポロジーソートを話しており、ちょうど問題を使って遊び、簡単なトポロジーソートをしています.
ACコード1(隣接テーブルで実装されている、やや挫折している…,初めて書く):

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
using namespace std;

int indegree[26];    //     
int visit[26];     //        

typedef struct node
{
	char data;
	struct node *p;
}list;

list zu[26];

void init()    //    
{
	for(int i=0; i<26; i++)
	{
		zu[i].p = NULL;
		zu[i].data = (char)(i+65);
	}
}

int topo(list zu[], int n)    //     ，      
{
	stack<int> s;
	node *xp;
	for(int i=0; i<26; i++)
	{
		if(visit[i] && !indegree[i]) s.push(i);
	}
	int count = 0;
	while(!s.empty())
	{
		int k = s.top(); s.pop(); count++;
		for(xp = zu[k].p; xp; xp = xp->p)
		{
			int l = xp->data - 65;
			if(!(--indegree[l])) s.push(l);
		}
	}
	if(count < n) return 0;
	else return 1;
} 

int main()
{
	int m;
	char a[5];
	while(scanf("%d", &m)!=EOF)
	{
		init();
		memset(indegree, 0, sizeof(indegree));
		memset(visit, 0, sizeof(visit));
		int num = 0;
		while(m--)
		{
			scanf("%s", a);
			if(!visit[a[0]-65])
			{
				visit[a[0]-65] = 1;
				num++;
			}
			if(!visit[a[2]-65])
			{
				visit[a[2]-65] = 1;
				num++;
			}
			if(a[1]=='<')
			{
				list *q;
				q = (struct node*)malloc(sizeof(node));
				q->data = a[2];
				q->p = zu[a[0]-65].p;
				zu[a[0]-65].p = q;
				indegree[a[2]-65]++;	
			}
			else 
			{
				list *q;
				q = (struct node*)malloc(sizeof(node));
				q->data = a[0];
				q->p = zu[a[2]-65].p;
				zu[a[2]-65].p = q;
				indegree[a[0]-65]++;	
			}
		}
		if(topo(zu, num)) printf("YES
");
		else printf("NO
");
	}
	return 0;
}

ACコード2(DFS判定回路!):

#include <cstdio> 
#include <cstring>
#include <algorithm>
using namespace std;

int map[30][30];
int vis[30]; 

int dfs(int cur)
{
    vis[cur]=-1;
    for(int i=0; i<26; ++i)
       if(map[cur][i])
	   {
          if(vis[i]==-1) return 0;
          if(!vis[i] && !dfs(i)) return 0;
       }
    vis[cur]=1;
    return 1;
}

int main()
{
    int m;
    char ch[5];
    while(scanf("%d", &m)!=EOF)
	{
        memset(vis, 0, sizeof(vis)); 
        memset(map, 0, sizeof(map));
        while(m--)
		{
            scanf("%s", ch);
            if(ch[1]=='>')
               map[ch[2]-'A'][ch[0]-'A']=1;
            else
               map[ch[0]-'A'][ch[2]-'A']=1;
        }
        int flag=0;
        for(int i=0; i<26; ++i)
           if(!vis[i])
             if(!dfs(i))
			 {
                flag=1;
                break;
             }
        if(flag)  printf("NO
");
        else printf("YES
");
    }    
    return 0;
}

Shinyでdebounceを使ってインプットの反映を遅らせる方法

Rで重回帰分析のステップワイズで特定の変数を残したい