SRM 608 DIV1 Middle - BigO （復習x）
問題
有向グラフが与えられる。
このうち、巨大な経路長Ｌを考え、そのＬの場合の数がＯ（Ｌ＾Ｋ）となるかを知りたい。
Ｏ（Ｌ＾Ｋ）となるときはＫを、そうでないときは-1を返す。
解き方
ある閉路に対して途中で分岐があるのであれば、経路長は２＾Ｌに増え続けるため-1となる。
逆に、そうでない閉路が存在すれば答えは存在する。
ただし、閉路でない場合はＬが巨大になりえないので、答えは０となる。
ある閉路からある閉路まで移動することができるとき、
最初の閉路でＬのうちいくつかの道を作り、次の経路で残りの数を選べるのでＬ＾１となる。
つまり、閉路間の最大距離がＫとなることがわかる。
同じ閉路に属するノードはＵＮＩＯＮ－ＦＩＮＤ木を用いて同じ集合とし、最後にＵＮＩON同士の最大距離を求めればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int un=1000;
int urank[1000],uparent[1000];
int d[60][60],d2[60][60];
class BigO {
public:
void union_init(){
FORE(i,0,un){
uparent[i]=i;
urank[i]=0;
}
}
int union_find(int x){
return (uparent[x]==x) ? x : (uparent[x]=union_find(uparent[x]));
}
void union_unit(int x,int y){
x=union_find(x),y=union_find(y);
if(x==y)return;
if(urank[x]<urank[y])uparent[x]=y;
else{
uparent[y]=x;
if(urank[x]==urank[y])urank[x]++;
}
}
int minK(vector<string> graph) {
int n=graph.size();
int nloop[n];
memset(nloop,0,sizeof(nloop));
FORE(i,0,n)FORE(j,0,n)d[i][j]=(graph[i][j]=='Y');
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)d[i][j]|=d[i][k]&&d[k][j];
union_init();
FORE(i,0,n){
FORE(j,0,n)if(i!=j&&graph[i][j]=='Y'&&d[j][i])nloop[i]++,union_unit(i,j);
if(nloop[i]>1)return -1;
}
if(count(nloop,nloop+n,1)==0)return 0;
int ret=0;
memset(d2,0,sizeof(d2));
FORE(i,0,n)FORE(j,0,n)if(nloop[i]&&nloop[j]&&d[i][j]&&union_find(i)!=union_find(j)){
d2[union_find(i)][union_find(j)]=1;
}
FORE(t,0,n)FORE(k,0,n)FORE(i,0,n)FORE(j,0,n){
if(i!=j&&j!=k&&k!=i&&d2[i][k]&&d2[k][j])d2[i][j]=d2[i][k]+d2[k][j];
ret=max(ret,d2[i][j]);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int un=1000;
int urank[1000],uparent[1000];
int d[60][60],d2[60][60];
class BigO {
public:
void union_init(){
FORE(i,0,un){
uparent[i]=i;
urank[i]=0;
}
}
int union_find(int x){
return (uparent[x]==x) ? x : (uparent[x]=union_find(uparent[x]));
}
void union_unit(int x,int y){
x=union_find(x),y=union_find(y);
if(x==y)return;
if(urank[x]<urank[y])uparent[x]=y;
else{
uparent[y]=x;
if(urank[x]==urank[y])urank[x]++;
}
}
int minK(vector<string> graph) {
int n=graph.size();
int nloop[n];
memset(nloop,0,sizeof(nloop));
FORE(i,0,n)FORE(j,0,n)d[i][j]=(graph[i][j]=='Y');
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)d[i][j]|=d[i][k]&&d[k][j];
union_init();
FORE(i,0,n){
FORE(j,0,n)if(i!=j&&graph[i][j]=='Y'&&d[j][i])nloop[i]++,union_unit(i,j);
if(nloop[i]>1)return -1;
}
if(count(nloop,nloop+n,1)==0)return 0;
int ret=0;
memset(d2,0,sizeof(d2));
FORE(i,0,n)FORE(j,0,n)if(nloop[i]&&nloop[j]&&d[i][j]&&union_find(i)!=union_find(j)){
d2[union_find(i)][union_find(j)]=1;
}
FORE(t,0,n)FORE(k,0,n)FORE(i,0,n)FORE(j,0,n){
if(i!=j&&j!=k&&k!=i&&d2[i][k]&&d2[k][j])d2[i][j]=d2[i][k]+d2[k][j];
ret=max(ret,d2[i][j]);
}
return ret;
}
};
