Codeforces #236 Div1 C. Strictly Positive Matrix

本番は1時間以上悩んだうえ、気が付いたら実装はあっさり。
http://codeforces.com/contest/403/problem/C

問題

NxNの行列Aがある。
対角成分は自然数で、それ以外の成分は0以上の整数である。
この行列を何乗かして全要素を正にできるか答えよ。

解法

N<=2000のため、実際に自乗するのにO(N^3)かけるとTLEする。

試しにどんなケースで全要素が0にならないか試してみると、以下のようになる。

* * * * *   * 0 0 0 *
0 1 1 1 0   * 1 1 1 *
0 1 1 1 0   * 1 1 1 *
0 1 1 1 0   * 1 1 1 *
* * * * *   * 0 0 0 *

左側についてはいくつかの行において、非0な要素がそれらの行番号以外の列にないケース。
例えば２～４行目は２～４列目以外0である。
転置した場合も同様で、右側は２～４列目は２～４行目以外0である。

よって元の行列が上記条件に当てはまるか見直せばよい。
本番は自分は以下のようにした。がi行→j行への有向パスの有無を示す隣接行列とみなしたとき、強連結成分分解をすると全要素が1つになれば題意を満たす。
上記処理を元行列Aとその転置行列に行えばよい。以下は本番に通した強連結成分分解のコード。

もう少し簡単に行う方法もある。
上記の条件を言い換えると「任意の行iから任意の行jに隣接行列Aを通し行けること」である。
よって行1からすべての行に行け、逆にすべての行から行1に戻れればよい。

どちらにしてもO(N^2)で実行できるので、なんとか間に合う。

int N;
int A[2010][2010];

class G {
public:
	static const int MV = 5000;
	vector<int> E[MV], RE[MV], NUM;
	vector<vector<int> > SC;
	int NV,vis[MV],GR[MV];
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear(); }}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c++);}
		SC.resize(c);
	}
};

void solve() {
	int f,i,j,k,l,x,y;
	
	G g;
	cin>>N;
	g.init(N);
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		if(A[y][x]>0) g.add_edge(y,x);
	}
	g.scc();
	if(g.SC.size()==1) _P("YES\n");
	else _P("NO\n");
}

まとめ

本番強連結成分分解に気づけて良かった。
ライブラリも作ってあったしね。