Тема: Блок схему для с++
#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;
}
Місто складається з N районів (1 ≤ N ≤ 100). Кожен район має свердловину для отримання води. Кожні дві свердловини з'єднані між собою трубою. По кожній трубі вода може текти тільки в одному напрямку. Внаслідок енергетичної кризи в кожен момент часу працює тільки одна свердловина. Оскільки система проектувалась без передбачення такого режиму роботи, деякі райони міста інколи залишаються без води.
Визначте, чи можна, змінивши напрямок протікання води у всіх трубах, підключених до однієї з свердловин, добитись безперервного водопостачання в місті.
Технічні умови
Вхідні дані
В першому рядку знаходиться число N - кількість районів (свердловин) в місті. В наступних N рядках для кожної свердловини вказується кількість і номери свердловин, з яких до неї надходить вода. Свердловини мають номери від 1 до N.
Вихідні дані
В єдиному рядку має бути одне число - 1 якщо, це можливо, або 0 в іншому випадку.
Приклад вхідних даних
4
0
1 1
2 1 2
3 1 2 3
Приклад вихідних даних
1