Pagini recente » Cod sursa (job #2290284) | Cod sursa (job #2652634) | Cod sursa (job #1481096) | Cod sursa (job #2787665) | Cod sursa (job #3252939)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<bool> viz;
void dfs(int nod, vector<vector<int>> &edges, vector<int> &add_to)
{
viz[nod] = true;
for(auto i : edges[nod])
if(!viz[i])
dfs(i, edges, add_to);
add_to.push_back(nod);
}
int main()
{
fin >> n >> m;
vector<vector<int>> rev_edges(n), edges(n);
vector<int> st;
viz.resize(n);
for(int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
x--;
y--;
edges[x].push_back(y);
rev_edges[y].push_back(x);
}
for(int nod = 0; nod < n; nod++)
{
if(!viz[nod])
dfs(nod, edges, st);
}
viz.clear();
viz.resize(n);
vector<vector<int>> ctc;
for(int i = st.size()-1; i >= 0; i--)
if(viz[st[i]] == 0)
{
ctc.push_back(vector<int>());
dfs(st[i], rev_edges, ctc.back());
}
fout << ctc.size() << "\n";
for(auto cm : ctc)
{
for(auto nod : cm)
fout << nod+1 << " ";
fout << "\n";
}
return 0;
}