Pagini recente » Cod sursa (job #2806192) | Cod sursa (job #1505912) | Cod sursa (job #521029) | Cod sursa (job #1740867) | Cod sursa (job #1548798)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nrc;
vector<vector<int>> G1, G2, cc;
vector<int> c;
vector<bool> s, s1;
stack<int> stk;
void Read();
void Df(int x);
void DfT(int x);
int main()
{
Read();
for (int i = 1; i <= n; i++)
if (!s[i]) Df(i);
int x;
while (!stk.empty())
{
x = stk.top(); stk.pop();
if (!s1[x])
{
nrc++;
c.clear();
DfT(x);
cc.push_back(c);
}
}
fout << nrc << '\n';
for (const auto & C : cc)
{
for (const auto & x : C)
fout << x << ' ';
fout << '\n';
}
return 0;
}
void DfT(int x)
{
s1[x] = true;
c.push_back(x);
for (const auto & e : G2[x])
if (!s1[e]) DfT(e);
}
void Df(int x)
{
s[x] = true;
for (const auto & e : G1[x])
if (!s[e]) Df(e);
stk.push(x);
}
void Read()
{
fin >> n >> m;
G1 = G2 = vector<vector<int>>(n + 1);
s = s1 = vector<bool>(n + 1);
for (int i = 1, x, y; i <= m; i++)
{
fin >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}