Moi_an_cuoi_maybetimeout

Maybe
 avatar
Kotori
c_cpp
2 months ago
1.3 kB
3
Indexable
Never
#pragma warning (disable : 4996)
#include<iostream>

using namespace std;

int T, N, M, v_start, v_end;
int canh[1005][2];
int cnt[105];
int canhke[105][105];
int res = 0;
int visited[105];
int trace[105];
int need[105][105];
int cnt_kq[105];
int ans[105];
int k;

void dfs(int u, int count)
{
	if (u == v_end)
	{
		
		for (int i = 0; i < count; i++)
		{
			ans[trace[i]]++;
		}
		k++;
		return;
	}

	for (int i = 0; i < cnt[u]; i++)
	{
		if (visited[canhke[u][i]] == 0)
		{
			visited[canhke[u][i]] = 1;
			trace[count] = canhke[u][i];
			dfs(canhke[u][i], count + 1);
			trace[count] = 0;
			visited[canhke[u][i]] = 0;
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		k = 0;
		res = 0;
		cin >> N >> M >> v_start >> v_end;
		for (int i = 0; i <= N; i++)
		{
			cnt[i] = 0;
			visited[i] = 0;
			ans[i] = 0;
		}

		for (int i = 0; i < M; i++)
		{
			cin >> canh[i][0] >> canh[i][1];
			canhke[canh[i][0]][cnt[canh[i][0]]++] = canh[i][1];
		}
		visited[v_start] = 1;
		trace[0] = v_start;
		dfs(v_start, 1);


		for (int i = 0; i <= N; i++)
		{
			if (ans[i] == k)
			{
				res++;
			}
		}
		cout << res - 2 << endl;
	}
	return 0;
}
Leave a Comment