Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
Sample Input
3
010
001
100
Sample Output
9
HINT
对于100%的数据，N不超过2000。
看到这题然后马上打了一个tarjan
然后对每一个强连通分量dfs，A了之后感觉有点奇怪，这个复杂度是多少来着，我好像算不出来，果断百度题解
然后大囧。。。。。。怎么好像正解是tarjan+拓扑排序+状态压缩，只搜到了一个和我一样的做法
然后我想到这样做其实可以随随便便卡掉，还是n三方，于是又打了一遍正解，加个拓扑和状态压缩
const
maxn=;
var
first,c,sum,dfn,low,z:array[..maxn*]of longint;
next,last:array[..maxn*maxn*]of longint;
flag:array[..maxn*]of boolean;
f:array[..maxn,..maxn]of boolean;
n,cnt,tot,ans,time,s:longint; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; procedure dfs(x:longint);
var
i:longint;
begin
inc(time);
dfn[x]:=time;
low[x]:=time;
inc(s);
z[s]:=x;
flag[x]:=true;
i:=first[x];
while i<> do
begin
if dfn[last[i]]= then
begin
dfs(last[i]);
if low[last[i]]<low[x] then low[x]:=low[last[i]];
end
else
if flag[last[i]] and (low[last[i]]<low[x]) then low[x]:=low[last[i]];
i:=next[i];
end;
if low[x]=dfn[x] then
begin
inc(cnt);
while z[s+]<>x do
begin
inc(sum[cnt]);
c[z[s]]:=cnt;
flag[z[s]]:=false;
dec(s);
end;
end;
end; procedure init;
var
i,j:longint;
cc:char;
begin
readln(n);
for i:= to n do
begin
for j:= to n do
begin
read(cc);
if cc='' then insert(i,j);
end;
readln;
end;
for i:= to n do
if dfn[i]= then dfs(i);
for i:= to n do
begin
j:=first[i];
while j<> do
begin
if f[c[i],c[last[j]]]=false then
begin
insert(n+c[i],n+c[last[j]]);
f[c[i],c[last[j]]]:=true;
end;
j:=next[j];
end;
end;
end; function dfs2(x:longint):longint;
var
i:longint;
begin
dfs2:=sum[x-n];
flag[x]:=true;
i:=first[x];
while i<> do
begin
if flag[last[i]]=false then inc(dfs2,dfs2(last[i]));
i:=next[i];
end;
end; procedure work;
var
i,j:longint;
begin
for i:= to cnt do
begin
for j:= to cnt do
flag[j+n]:=false;
inc(ans,sum[i]*dfs2(i+n));
end;
writeln(ans);
end; begin
init;
work;
end.
const
maxn=;
var
first,c,sum,dfn,low,z,d:array[..maxn*]of longint;
next,last:array[..maxn*maxn*]of longint;
flag:array[..maxn*]of boolean;
ff:array[..maxn,..maxn]of boolean;
n,cnt,tot,ans,time,s:longint; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; procedure dfs(x:longint);
var
i:longint;
begin
inc(time);
dfn[x]:=time;
low[x]:=time;
inc(s);
z[s]:=x;
flag[x]:=true;
i:=first[x];
while i<> do
begin
if dfn[last[i]]= then
begin
dfs(last[i]);
if low[last[i]]<low[x] then low[x]:=low[last[i]];
end
else
if flag[last[i]] and (low[last[i]]<low[x]) then low[x]:=low[last[i]];
i:=next[i];
end;
if low[x]=dfn[x] then
begin
inc(cnt);
while z[s+]<>x do
begin
inc(sum[cnt]);
c[z[s]]:=cnt;
flag[z[s]]:=false;
dec(s);
end;
end;
end; procedure init;
var
i,j:longint;
cc:char;
begin
readln(n);
for i:= to n do
begin
for j:= to n do
begin
read(cc);
if cc='' then insert(i,j);
end;
readln;
end;
for i:= to n do
if dfn[i]= then dfs(i);
for i:= to n do
begin
j:=first[i];
while j<> do
begin
if (ff[c[i],c[last[j]]]=false) and (c[i]<>c[last[j]]) then
begin
insert(n+c[i],n+c[last[j]]);
inc(d[c[last[j]]]);
ff[c[i],c[last[j]]]:=true;
end;
j:=next[j];
end;
end;
end; var
q:array[..maxn]of longint;
f:array[..maxn,..]of longint;
l,r:longint; procedure work;
var
i,j,k,tmp:longint;
begin
l:=;
r:=;
for i:= to cnt do
if d[i]= then
begin
inc(r);
q[r]:=i;
end;
while l<=r do
begin
j:=first[q[l]+n];
while j<> do
begin
dec(d[last[j]-n]);
if d[last[j]-n]= then
begin
inc(r);
q[r]:=last[j]-n;
end;
j:=next[j];
end;
inc(l);
end;
for i:=r downto do
begin
f[q[i],q[i] div ]:=<<(q[i]mod );
j:=first[q[i]+n];
while j<> do
begin
for k:= to cnt div do
f[q[i],k]:=f[q[i],k]or f[last[j]-n,k];
j:=next[j];
end;
end;
for i:= to cnt do
begin
tmp:=;
for j:= to cnt do
if f[i,j div ] and (<<(j mod ))> then inc(tmp,sum[j]);
inc(ans,tmp*sum[i]);
end;
writeln(ans);
end; begin
init;
work;
end.