Pagini recente » Cod sursa (job #1267863) | Cod sursa (job #2550618) | Cod sursa (job #499217) | Cod sursa (job #1852538) | Cod sursa (job #2863403)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, nrctc, ver[100001];
vector < int > g[100001], gt[100001], v[100001];
stack < int > st;
void dfsp (int nc) {
ver[nc] = 1;
for (int i = 0; i < g[nc].size (); i++) {
int nv = g[nc][i];
if (not ver[nv])
dfsp (nv);
}
st.push (nc);
}
void dfsm (int nc) {
ver[nc] = 2;
v[nrctc].push_back (nc);
for (int i = 0; i < gt[nc].size (); i++) {
int nv = gt[nc][i];
if (ver[nv] == 1)
dfsm (nv);
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back (y);
gt[y].push_back (x);
}
for (int i = 1; i <= n; i++)
if (not ver[i])
dfsp (i);
while (not st.empty ()) {
int nc = st.top ();
if (ver[nc] == 1) {
nrctc++;
dfsm (nc);
}
st.pop ();
}
fout << nrctc << '\n';
for (int i = 1; i <= nrctc; i++) {
for (int j = 0; j < v[i].size (); j++)
fout << v[i][j] << ' ';
fout << '\n';
}
return 0;
}