Pagini recente » Istoria paginii runda/sa_fac_schema/clasament | Cod sursa (job #1646066) | Cod sursa (job #807748) | Cod sursa (job #3144060) | Cod sursa (job #2718974)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int N = 200001;
int n, viz_a[N], viz_b[N], comp[N];
vector<int>a[N], b[N], mat[N];
void dfs_a(int nod)
{
viz_a[nod] = 1;
for (auto i: a[nod])
if (viz_a[i] == 0)
dfs_a(i);
}
void dfs_b(int nod)
{
viz_b[nod] = 1;
for (auto i : b[nod])
if (viz_b[i] == 0)
dfs_b(i);
}
int main()
{
int m, i, j, x, y, k = 0;
cin >> n >> m;
for (i = 1; i <= m; i++)
{
cin >> x >> y;
a[x].push_back(y);
b[y].push_back(x);
}
for (i = 1; i <= n; i++)
{
if (comp[i] == 0)
{
for (j = 1; j <= n; j++)
viz_a[j] = viz_b[j] = 0;
dfs_a(i);
dfs_b(i);
k++;
for (j = 1; j <= n; j++)
{
if (viz_a[j] && viz_b[j])
{
comp[j] = k;
mat[k].push_back(j);
}
}
}
}
cout << k << "\n";
for (i = 1; i <= n; i++)
{
for (j = 0; j < mat[i].size(); j++)
cout << mat[i][j] << ' ';
cout << "\n";
}
return 0;
}