F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2208 >> dfs
GXZlegend @ 2017-10-31 15:53:41
[ Quote ] [ Edit ] [ Delete ] 1#
这不是O(nm)=O(n^3)的吗?只不过数据太水了..
OwenOwl @ 2017-11-23 21:17:58
[ Quote ] [ Edit ] [ Delete ] 2#
cnlarryzhong是暴力之神!
cnlarryzhong @ 2017-11-23 23:21:17
[ Quote ] [ Edit ] [ Delete ] 3#
O(n^2)
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2010;
int n, _count, vis[maxn];
vector<int> G[maxn];

void dfs(int u) {
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
if (!vis[G[u][i]]) {
dfs(G[u][i]);
}
}
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
char ch;
for (int j = 1; j <= n; j++) {
cin >> ch;
if (ch == '1') {
G[i].push_back(j);
}
}
}
for (int i = 1; i <= n; i++) {
memset(vis, false, sizeof(vis));
dfs(i);
for (int j = 1; j <= n; j++) {
_count += vis[j];
}
}
cout << _count << endl;
return 0;
}
myjs69 @ 2017-11-25 10:57:41
[ Quote ] [ Edit ] [ Delete ] 4#
cnlarryzhong太神了!!
Azrael_Death @ 2017-11-25 11:19:17
[ Quote ] [ Edit ] [ Delete ] 5#
cnlarryzhong太神了!!
Drench @ 2017-11-26 21:29:06
[ Quote ] [ Edit ] [ Delete ] 6#
@cnlarryzhong 这是O(n^2)?你可能需要学习一下怎么算复杂度2333
cnlarryzhong @ 2017-12-01 18:40:50
[ Quote ] [ Edit ] [ Delete ] 7#
@Drench 是 O(n^2) 啊!
[Top] [Previous Page] [Next Page]

HOME Back