连续两天大凶(?
by zl_just @ 2019-05-02 00:23:57
@[zl_just](/space/show?uid=125925)
这是我的代码，您可以看一下：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
#define reg register
#define inf 0x3f3f3f3f
#define p 998244353
#define N 2007
using namespace std;
vector<int> adj[N],g[N];
int low[N],dfn[N],stk[N],clr[N],w[N],ans[N];
bool vis[N];
int top,cnt,scc,n;
inline void read(int &x);
void print(int x);
void tarjan(int u);
inline int min(int x,int y);
void dfs(int u,int f);
int main(){
reg int u,v,l,res = 0;
read(n);
char c;
for(reg int i=1;i<=n;++i){
for(reg int j=1;j<=n;++j){
c = getchar();
while(c!='0'&&c!='1') c = getchar();
if(c=='0') continue;
adj[i].push_back(j);
}
}
for(reg int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(u=1;u<=n;++u){ //缩点
l = adj[u].size();
for(reg int i=0;i<l;++i){
v = adj[u][i];
if(clr[u]==clr[v]) continue;
g[clr[u]].push_back(clr[v]);
}
}
for(reg int i=1;i<=n;++i) ++w[clr[i]]; //记一个强连通分量的权值为其包含的节点个数
for(reg int i=1;i<=scc;++i){
memset(vis,0,sizeof(vis));
dfs(i,i);
}
for(reg int i=1;i<=n;++i) res += ans[clr[i]];
print(res);
return 0;
}
void dfs(int u,int f){
ans[f] += w[u];
vis[u] = true;
int v,l = g[u].size();
for(int i=0;i<l;++i){
v = g[u][i];
if(vis[v]) continue;
dfs(v,f);
}
}
void tarjan(int u){
low[u] = dfn[u] = ++cnt;
vis[u] = true;
stk[++top] = u;
int v,l = adj[u].size();
for(int i=0;i<l;++i){
v = adj[u][i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u]!=dfn[u]) return;
++scc;
do{
vis[stk[top]] = false;
clr[stk[top]] = scc;
--top;
}while(stk[top+1]!=u);
}
inline int min(int x,int y){
return x<y?x:y;
}
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
void print(int x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
```
by NaCly_Fish @ 2019-05-02 02:18:43
@[zl_just](/space/show?uid=125925) 您的问题在于，您缩点的时候，根本没有重新建图(即没有连边)
by NaCly_Fish @ 2019-05-02 02:31:27
给您改好了qwq
[评测记录](https://www.luogu.org/recordnew/show/18688707)
by NaCly_Fish @ 2019-05-02 02:36:40
感谢大佬
`rebuild()`的确有问题，虽然`dfs()`也是,请原谅我太弱了，我还是没看出您的`rebuild`的和我有什么区别，~~虽然把您的`rebuild`粘贴过来就A了，顺便盗了您的`dfs`~~
by zl_just @ 2019-05-02 08:04:50