Pagini recente » Cod sursa (job #1470396) | Cod sursa (job #1946965) | Cod sursa (job #2225974) | Cod sursa (job #711930) | Cod sursa (job #2928876)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int node, stack<int> &st, vector<int> &vis, vector<vector<int>> la)
{
vis[node] = 1;
for (auto it : la[node])
if (!vis[it])
dfs(it, st, vis, la);
st.push(node);
}
vector<int> revDfs(int node, vector<int>& vis, vector<vector<int>> transp)//, ofstream& fout)
{
vector<int> res;
res.push_back(node);
//fout << node << " ";
vis[node] = 1;
for (auto it : transp[node])
if (!vis[it])
revDfs(it, vis, transp);//, fout);
//fout << endl;
return res;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
vector<vector<int>> la(n);
for (int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
la[x].push_back(y);
}
fin.close();
stack<int> st;
vector<int> vis(n, 0);
for (int i = 0; i < n; i++)
if (!vis[i])
dfs(i, st, vis, la);
vector<vector<int>> transp(n);
for (int i = 0; i < n; i++)
{
vis[i] = 0;
for (auto &it : la[i])
transp[it].push_back(i);
}
vector<vector<int>> res;
int n_comp = 0;
while (!st.empty())
{
int node = st.top();
st.pop();
if (!vis[node])
{
//n_comp++;
res.push_back(revDfs(node, vis, transp));//, fout);
//fout << endl;
}
}
fout << res.size() << endl;
for (int i = 0; i < res.size(); i++)
{
for (int j = 0; j < res[i].size(); j++)
fout << res[i][j] << ' ';
fout << endl;
}
fout.close();
}