Теория графов. Задача №40 с e-olimp. Водопровод.

[sublemate]

Совершенно не понимаю задачу , помогите чем можете...

Город состоит из N районов (1 ≤ N ≤ 100).
Каждый регион имеет скважину для получения воды.
Каждые две скважины соединены между собой трубой.
По каждой трубе вода может течь только в одном направлении.
Вследствие энергетического кризиса в каждый момент времени работает только одна скважина.
Определите, можно, изменив направление протекания воды во всех трубах, подключенных к одной из скважин, добиться непрерывного водоснабжения в городе.
Входные данные
В первой строке находится число N - количество районов (скважин) в городе. В следующих N строках для каждой скважины указывается количество и номера скважин, из которых к ней поступает вода. Скважины имеют номера от 1 до N.

Выходные данные
В единственной строке должно быть одно число - 1 если это возможно, или 0 в противном случае.

Пример:
Входные данные
4
0
1 1
2 1 2
3 1 2 3
Выходные данные
1

[Poma][a]

Какой язык?
Решить можно через перебор вершин, инверсию ее ребер. И запуска dfs (наверное)
Точно есть решение оптимальнее, но это после

Если кто-то будет сдавать там С++'шный код, то не забывайте про endl

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t-1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);
		
		dfs(v, i);

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот такой код набирает 92%. Не проходит 3-ий тест. Там должен быть ответ 0 (а у меня видимо 1).

Но это неправильно..
Пример :

3
1 3
1 1
1 2

Можем поменять у 1 :
Получим

3
1 2
0
2 1 2

Можем запустить из 2-ой и всё получится

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t - 1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);

		dfs(v, i);

		for (int j = 0; j < n; j++)
		{
			if (mark[j])
				for (int k = 0; k < n; k++)
					if (v[j][k] != 0 && !mark[k])
						dfs(v, j);
		}

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот такой код работает прально (на моем тесте)
Но снова 92

Потом поищу косяк


Ах да.. Возможно я просто неправильно понял условие

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	if (n == 2)
	{
		cout << 0 << endl;
		return 0;
	}

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t - 1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);

		dfs(v, i);

		for (int j = 0; j < n; j++)
		{
			if (mark[j])
				for (int k = 0; k < n; k++)
					if (v[j][k] != 0 && !mark[k])
						dfs(v, j);
		}

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот это зашло..
Ничего не понимаю. Почему решения для N = 2 не существует? Оно есть при любом раскладе, разве нет?
Думаю, что завтра утром, на свежую голову, все прояснится

[Poma][a]

Ха! И это решение тоже неправильно.
С таким dfs'Ом. Я был неправ. Нужно представить, что граф неориентированный

Не поминаю почему такие слабые тесты.
Да еще с 2-ой снова ничего не понятно
Ужасть

[Poma][a]

Ха. Почти все прояснилось. Ответом на задачу будет всегда 1.
Вся фишка в том, что граф при dfs можно представить как НЕориентированный. Тогда решение не будет только при двух и более компонент связности. Чего не может быть по условию

[sublemate]

Так то да , но мне как-то нужно ето оформить , ето является одним из заданий курсовой ...(
Какой код был найболее удачным ?
Просто мой вариант какой-то очень странный...

[sublemate]

Сообщение от Poma][a

Ха. Почти все прояснилось. Ответом на задачу будет всегда 1.
Вся фишка в том, что граф при dfs можно представить как НЕориентированный. Тогда решение не будет только при двух и более компонент связности. Чего не может быть по условию

И какой код успешно засчитали на e-olimp ?

[Poma][a]

if (n == 2) cout << 0 << endl;
else cout << 1 << endl;

Про 1 : можно красиво доказать..
Про 0 : я не знаю почему он вообще существует

[sublemate]

Сообщение от Poma][a

if (n == 2) cout << 0 << endl;
else cout << 1 << endl;

Про 1 : можно красиво доказать..
Про 0 : я не знаю почему он вообще существует

#include <stdio.h>
int main()
{
short n;
scanf_s("%hd",&n);
n>1&&n<3?printf("0\n"):printf("1\n");
return 0;
}

Етот код , кстати , в олимпе так же 100%, странно однако...
И тогда не понимаю как к етой задачи составить блок схему

[Poma][a]

Етот код , кстати , в олимпе так же 100%, странно однако...

Почему?
Почти тот же самый код.
Только странное сравнение, которое эквивалентно двойке

И тогда не понимаю как к етой задачи составить блок схему

Ха. Забавная логика. Решать задачи на графы, но не суметь бахнуть схемку
Тут точно без меня

[Robbyster]

Сообщение от Poma][a

Какой язык?
Решить можно через перебор вершин, инверсию ее ребер. И запуска dfs (наверное)
Точно есть решение оптимальнее, но это после

Если кто-то будет сдавать там С++'шный код, то не забывайте про endl

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t-1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);
		
		dfs(v, i);

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот такой код набирает 92%. Не проходит 3-ий тест. Там должен быть ответ 0 (а у меня видимо 1).

Но это неправильно..
Пример :

3
1 3
1 1
1 2

Можем поменять у 1 :
Получим

3
1 2
0
2 1 2

Можем запустить из 2-ой и всё получится

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t - 1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);

		dfs(v, i);

		for (int j = 0; j < n; j++)
		{
			if (mark[j])
				for (int k = 0; k < n; k++)
					if (v[j][k] != 0 && !mark[k])
						dfs(v, j);
		}

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот такой код работает прально (на моем тесте)
Но снова 92

Потом поищу косяк


Ах да.. Возможно я просто неправильно понял условие

#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<bool> mark;

void dfs(const vector<vector<int> >& v, int k)
{
	mark[k] = false;

	for (int i = 0; i < v.size(); i++)
		if (v[k][i] != 0 && mark[i])
			dfs(v, i);
}

int main()
{
	int n;
	cin >> n;

	if (n == 2)
	{
		cout << 0 << endl;
		return 0;
	}

	vector<vector<int> > v(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int t;
			cin >> t;
			v[i][t - 1] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);

		mark.assign(n, true);

		dfs(v, i);

		for (int j = 0; j < n; j++)
		{
			if (mark[j])
				for (int k = 0; k < n; k++)
					if (v[j][k] != 0 && !mark[k])
						dfs(v, j);
		}

		if (accumulate(mark.begin(), mark.end(), 0) == 0)
		{
			cout << 1 << endl;
			return 0;
		}

		for (int j = 0; j < n; j++)
			swap(v[i][j], v[j][i]);
	}

	cout << 0 << endl;

	return 0;
}

Вот это зашло..
Ничего не понимаю. Почему решения для N = 2 не существует? Оно есть при любом раскладе, разве нет?
Думаю, что завтра утром, на свежую голову, все прояснится

Привет, есть вопросы по задаче, можете помочь?