为什么给我判错?
查看原帖
为什么给我判错?
481621
Zhang_Wenjie楼主2024/7/30 17:25

rt,数据下下来本地跑答案是对的,交上去给我判 wa神奇?

#include <bits/stdc++.h>
#define re register int 

using namespace std;
typedef long long LL;
const int N = 1e3 + 10;

int T, n, m;
int dfn[N], low[N], idx, root = 1, cnt;
bool cut[N];

stack<int> stk;
vector<int> g[N], vdcc[N];

void tarjan(int u)
{
	low[u] = dfn[u] = ++ idx;
	stk.push(u);
	
	int kid = 0;
	for (re i = 0; i < g[u].size(); i ++)
	{
		int v = g[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (dfn[u] <= low[v])
			{
				kid ++;
				if (u != root || kid > 1) cut[u] = true;
				
				cnt ++;
				int ver;
				do
				{
					ver = stk.top(); stk.pop();
					vdcc[cnt].push_back(ver);
				}while (ver != v);
				vdcc[cnt].push_back(u);

			}
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	while (cin >> m, m)
	{
		for (re i = 1; i <= N; i ++)
		{
			g[i].clear();
			vdcc[i].clear();
			dfn[i] = low[i] = 0;
			cut[i] = false;
		}
		n = idx = cnt = 0;
		
		for (re i = 1; i <= m; i ++)
		{
			int x, y; cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
			n = max(n, max(x, y));
		}
		tarjan(1);
		
		LL ans1 = 0, ans2 = 1;
		for (re i = 1; i <= cnt; i ++)
		{
			int siz = vdcc[i].size(), k = 0;
			
			for (re j = 0; j < siz; j ++)
				k += (cut[vdcc[i][j]] ? 1 : 0);
			if (k == 1) ans1 ++, ans2 *= (siz - 1);
			if (k == 0) ans1 += 2, ans2 *= siz * (siz - 1) / 2;
		}
		cout << "Case " << ++ T << ": " << ans1 << ' ' << ans2 << '\n';
	}
	
	return 0;
}
2024/7/30 17:25
加载中...