2020-team3-012

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[2005][2005];
int id[2005][2005], idx;
int g[4000005][5];
int vis[4000005], low[4000005], dfn[4000005], num, cnt;
void add(int x, int y) {
    g[x][++ g[x][0]] = y;
    g[y][++ g[y][0]] = x;
}

int tmp[4000005];

int main() {
#ifndef ONLINE_JUDGE
    freopen("G.in", "r", stdin);
#endif
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%s", s[i] + 1);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (s[i][j] == '.')
                id[i][j] = ++ idx;
    const int dx[4] = {0, +1};
    const int dy[4] = {+1, 0};
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (s[i][j] == '.') {
                for (int k = 0; k < 2; k ++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (1 <= ni && ni <= n && 1 <= nj && nj <= m && s[ni][nj] == '.')
                        add(id[i][j], id[ni][nj]);
                }
            }
    for (int i = 1; i <= idx; i ++)
        if (vis[i] == 0) {
            cnt ++;
            stack<pair<int, int> > stk;
            stk.push(make_pair(i, 0));
            while (!stk.empty()) {
                int x = stk.top().first, pr = stk.top().second;
                if (vis[x] == 0) {
                    vis[x] = 1, low[x] = dfn[x] = ++ num;
                    tmp[x] = -1;
                    if (pr)
                        tmp[x] ++;
                    for (int k = 1; k <= g[x][0]; k ++) {
                        int y = g[x][k];
                        if (y != pr) {
                            if (vis[y] == 0)
                                stk.push(make_pair(y, x));
                            else if (vis[y] == 1)
                                low[x] = min(low[x], dfn[y]);
                        }
                    }
                }
                else if (vis[x] == 1) {
                    stk.pop();
                    vis[x] = 2;
                    if (pr) {
                        low[pr] = min(low[pr], low[x]);
                        tmp[pr] += 1;
                        if (low[x] < dfn[pr])
                            tmp[pr] -= 1;
                    }
                }
                else if (vis[x] == 2)
                    stk.pop();
            }
        }
    printf("%d\n", cnt + *max_element(tmp + 1, tmp + idx + 1));
    return 0;
}

#include

using namespace std;

int n, m;

char s[2005][2005];

int id[2005][2005], idx;

int g[4000005][5];

int vis[4000005], low[4000005], dfn[4000005], num, cnt;

void add(int x, int y) {

g[x][++ g[x][0]] = y;

g[y][++ g[y][0]] = x;

}

int tmp[4000005];

int main() {

#ifndef ONLINE_JUDGE

freopen("G.in", "r", stdin);

#endif

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++)

scanf("%s", s[i] + 1);

for (int i = 1; i <= n; i ++)

for (int j = 1; j <= m; j ++)

if (s[i][j] == '.')

id[i][j] = ++ idx;

const int dx[4] = {0, +1};

const int dy[4] = {+1, 0};

for (int i = 1; i <= n; i ++)

for (int j = 1; j <= m; j ++)

if (s[i][j] == '.') {

for (int k = 0; k < 2; k ++) {

int ni = i + dx[k], nj = j + dy[k];

if (1 <= ni && ni <= n && 1 <= nj && nj <= m && s[ni][nj] == '.')

add(id[i][j], id[ni][nj]);

}

}

for (int i = 1; i <= idx; i ++)

if (vis[i] == 0) {

cnt ++;

stack > stk;

stk.push(make_pair(i, 0));

while (!stk.empty()) {

int x = stk.top().first, pr = stk.top().second;

if (vis[x] == 0) {

vis[x] = 1, low[x] = dfn[x] = ++ num;

tmp[x] = -1;

if (pr)

tmp[x] ++;

for (int k = 1; k <= g[x][0]; k ++) {

int y = g[x][k];

if (y != pr) {

if (vis[y] == 0)

stk.push(make_pair(y, x));

else if (vis[y] == 1)

low[x] = min(low[x], dfn[y]);

}

}

}

else if (vis[x] == 1) {

stk.pop();

vis[x] = 2;

if (pr) {

low[pr] = min(low[pr], low[x]);

tmp[pr] += 1;

if (low[x] < dfn[pr])

tmp[pr] -= 1;

}

}

else if (vis[x] == 2)

stk.pop();

}

}

printf("%d\n", cnt + *max_element(tmp + 1, tmp + idx + 1));

return 0;

}