Pagini recente » Cod sursa (job #2055614) | Cod sursa (job #2075050) | Solutii preONI 2007, Runda 3 | Cod sursa (job #2180897) | Cod sursa (job #2928890)
#include <fstream>
#include <vector>
using namespace std;
void dfs(int node, vector<int> vis, vector<vector<int>> la, vector<int> s)
{
vis[node] = 1;
for (auto i : la[node])
if (!vis[i]) dfs(i, vis, la, s);
s.push_back(node);
}
void revDfs(int node, vector<int> vis, vector<vector<int>> scc, vector<vector<int>> transp, int nr_comp)
{
vis[node] = 0;
scc[nr_comp].push_back(node);
for (auto i : transp[node])
if (vis[i])
revDfs(i, vis, scc, transp, nr_comp);
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> vis, s, v;
int n, m, nr_comp = 0;
fin >> n >> m;
vector<vector<int>> la(n), transp(n), scc;
for (int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
la[x].push_back(y);
transp[y].push_back(x);
}
fin.close();
for (int i = 0; i < n; i++)
if (!vis[i])
dfs(i, vis, la, s);
while (!s.empty())
{
int node = s.back();
s.pop_back();
if (vis[node])
{
scc.push_back(v);
revDfs(node, vis, scc, transp, nr_comp);
nr_comp++;
}
}
fout << nr_comp<< endl;
for (auto i : scc)
{
for (auto j : i)
fout << j << " ";
fout << endl;
}
fout.close();
}