bjoi 2009 函数依赖强连通分量

对于30%的测试数据，满足只有二元联系(即不存在函数依赖左边或右边的
属性个数超过 1 个)。
对于 40%的测试数据，满足N ≤ 5。
对于 70%的测试数据，满足M ≤ 100。
对于100%的测试数据，满足 1 ≤ N ≤ 10, 1 ≤ M ≤ 1000。

思路：因为n非常小

我们可以把2^n个关系全部列出来

按照题目的关系建立有向图

求强连通分量缩点拓扑排序

答案就是某个节点自己在头节点中，而他的真子集都不在

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 #define MAXN (1<<10)+1
  8 #define MAXM 1<<22
  9 struct node
 10 {
 11     int num;
 12     node *next;
 13 };
 14 node *graph[MAXN],*grapht[MAXN],*graphnew[MAXN];
 15 node memo[MAXM];
 16 bool use[MAXN],visit[MAXN][MAXN];
 17 int finish[MAXN],cnt[MAXN],mark[MAXN],ans[MAXN];
 18 int n,m,top=0,t=0,sum=0,color=0;
 19 pair<int,int> a[MAXN];
 20 char c[30];
 21 bool cmp(int x,int y)
 22 {
 23     for(int i=0;i<11;i++)
 24     {
 25         if(((1<<i)&x)==(1<<i)&&((1<<i)&y)!=(1<<i))
 26             return 1;
 27         if(((1<<i)&x)!=(1<<i)&&((1<<i)&y)==(1<<i))
 28             return 0;
 29     }
 30 
 31 }
 32 void add(int x,int y,node *graph[])
 33 {
 34     node *p=&memo[top++];
 35     p->num=y; p->next=graph[x]; graph[x]=p;
 36 }
 37 void dfs(int i)
 38 {
 39     use[i]=1;
 40     for(node *p=graph[i];p;p=p->next)
 41         if(!use[p->num])
 42             dfs(p->num);
 43     finish[++t]=i;
 44 }
 45 void dfst(int i)
 46 {
 47     use[i]=1;
 48     mark[i]=color;
 49     cnt[color]++;
 50     for(node *p=grapht[i];p;p=p->next)
 51         if(!use[p->num])
 52             dfst(p->num);
 53 }
 54 
 55 void connect()
 56 {
 57     memset(use,0,sizeof(use));
 58     int i;
 59     for(i=1;i<n;i++)
 60         if(!use[i])
 61             dfs(i);
 62     memset(use,0,sizeof(use));
 63     for(i=t;i>0;i--)
 64     if(!use[finish[i]])
 65     {
 66         color++;
 67         dfst(finish[i]);
 68     }
 69 }
 70 void reduce()
 71 {
 72     memset(visit,0,sizeof(visit));
 73     int i;
 74     for(i=1;i<n;i++)
 75     for(node *p=graph[i];p;p=p->next)
 76     {
 77         if(visit[mark[i]][mark[p->num]]==0&&mark[i]!=mark[p->num])
 78         {
 79             visit[mark[i]][mark[p->num]]=1;
 80             add(mark[i],mark[p->num],graphnew);
 81         }
 82     }
 83 }
 84 void solve()
 85 {
 86     t=0;
 87     memset(ans,0,sizeof(ans));
 88     memset(use,0,sizeof(use));
 89     int i,j,k;
 90     for(i=1;i<n;i++)
 91     if(mark[i]==1)
 92     {
 93         for(j=1;j<n;j++)
 94             if((i&j)==j&&mark[j]==1&&i!=j)
 95                 break;
 96         if(j==n) 
 97             ans[++t]=i;
 98     }
 99     printf("%d\n",t);
100     sort(ans+1,ans+t+1,cmp);
101     for(i=1;i<=t;i++)
102     {
103         for(j=0;j<11;j++)
104             if((ans[i]&(1<<j))==(1<<j))
105                 printf("%c",('A'+j));
106         printf("\n");
107     }
108 }
109 
110 int main()
111 {
112     memset(visit,0,sizeof(visit));
113     memset(cnt,0,sizeof(cnt));
114     memset(graph,0,sizeof(graph));
115     memset(grapht,0,sizeof(grapht));
116     memset(graphnew,0,sizeof(graphnew));
117     memset(use,0,sizeof(use));
118     scanf("%d%d",&n,&m);
119     n=(1<<n);
120     int i,j,x,l,y,k;
121     for(i=1;i<=m;i++)
122     {
123         x=y=0;
124         scanf("%s",c);
125         l=strlen(c);
126         for(j=0;c[j]!='-';j++)
127             x=x|(1<<(c[j]-'A'));
128         j=j+2;
129         for(j;j<l;j++)
130             y=y|(1<<(c[j]-'A'));
131         a[i].first=x; a[i].second=y;
132     }
133     for(i=1;i<n;i++)
134         for(k=1;k<=m;k++)
135             if((i&a[k].first)==a[k].first)
136                 for(j=1;j<n;j++)
137                     if(((i|a[k].second)&j)==j)
138                         visit[i][j]=1;
139     for(i=1;i<n;i++)
140         for(j=1;j<n;j++)
141             if(visit[i][j])
142             {
143                 add(i,j,graph);
144                 add(j,i,grapht);
145             }
146 
147     connect();
148     reduce();
149     solve();
150     return 0;
151 }

bjoi 2009 函数依赖 强连通分量

bjoi 2009 函数依赖强连通分量