模板题 WA 85pts
查看原帖
模板题 WA 85pts
183603
SUNCHAOYI废物生成器楼主2022/8/17 08:10

看到有两个新的模板题,想着复习一下但是就 85pts85pts 一直 WA:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXM = 2e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,cnt,times,bcc_cnt;
int head[MAXM << 1],to[MAXM << 1],nxt[MAXM << 1],dfn[MAXN],low[MAXN]; 
void add (int u,int v);
void dfs (int u,int fa);
stack <int> s;
vector <int> bcc[MAXN];
int main ()
{
//	freopen (".in","r",stdin);
//	freopen ("1.out","w",stdout);
	n = read ();m = read ();
	for (int i = 1;i <= m;++i)
	{
		int u = read (),v = read ();
		add (u,v);add (v,u);
	}
	for (int i = 1;i <= n;++i)
		if (!dfn[i]) dfs (i,-1);
	printf ("%d\n",bcc_cnt);
	for (int i = 1;i <= bcc_cnt;++i)
	{
		printf ("%d ",bcc[i].size ());
		for (int j = 0;j < bcc[i].size ();++j) printf ("%d ",bcc[i][j]);
		puts ("");
	}
	return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
	{
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
	{
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void add (int u,int v)
{
	to[++cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
void dfs (int u,int fa)
{
	dfn[u] = low[u] = ++times;
	s.push (u);
	for (int i = head[u];i;i = nxt[i])
	{
		int v = to[i];
		if (!dfn[v])
		{
			dfs (v,u);//dfs (v,i)
			low[u] = min (low[u],low[v]);
		}
		else if (v != fa && dfn[v] < dfn[u]) low[u] = min (low[u],dfn[v]);//i != (fa ^ 1)
	}
	if (low[u] == dfn[u])
	{
		++bcc_cnt;
		while (1)
		{
			int x = s.top ();s.pop ();
			bcc[bcc_cnt].push_back (x);
			if (u == x) break;
		}
	}
}

为啥这样只能拿 85pts85pts?错在哪里了呢?

改成初始 cnt = 1,打注释的地方变为 ii 而不是 vv 后才能过,不是很理解,求解释!

2022/8/17 08:10
加载中...