Pagini recente » Cod sursa (job #445197) | Cod sursa (job #2604118) | Cod sursa (job #496153) | Cod sursa (job #2155894) | Cod sursa (job #2784603)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> lan[100000];
vector<int> lat[100000];
int n,m;
int pls[100000];
int mns[100000];
// in asta memorez un nod care a fost deja atribuit unei comp conexe
int vist[100000];
void dfs(int nod, vector<int> la[], int vis[])
{
vis[nod] = 1;
for (auto& el: la[nod])
{
if (!vis[el])
dfs(el, la, vis);
}
}
int main()
{
in >> n >> m;
for (int i = 0; i < m; i++)
{
int n1, n2;
in >> n1 >> n2;
lan[n1-1].push_back(n2-1);
lat[n2-1].push_back(n1-1);
}
int nr_total = 0;
vector<vector<int>> res(100000);
for (int i = 0; i < n; i++)
{
if (vist[i])
continue;
dfs(i, lan, pls);
dfs(i, lat, mns);
for (int i = 0; i < n; i++)
{
if (pls[i] == 1 && mns[i] == 1)
{
res[nr_total].push_back(i);
vist[i] = 1;
}
}
nr_total ++;
// reset mns and pls
for (int i = 0; i < n; i++)
{
pls[i] = 0;
mns[i] = 0;
}
}
out << nr_total << '\n';
for (int i = 0; i < nr_total; i++)
{
for (auto& el: res[i])
out << el+1 << ' ';
out << '\n';
}
return 0;
}