Pagini recente » Cod sursa (job #3280151) | Cod sursa (job #1396409) | Cod sursa (job #2120733) | Cod sursa (job #1782987) | Cod sursa (job #1609799)
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> s;
vector<int> L1[100010];
vector<int> L2[100010];
bitset<100010> v;
vector<int> vec[100010];
int nr = 0;
void DFS1(int x)
{
v[x] = 1;
for (int i = 0;i < L1[x].size();++i)
if (v[L1[x][i]] == 0)
DFS1(L1[x][i]);
s.push_back(x);
}
void DFS2(int x)
{
v[x] = 1;
for (int i = 0;i < L2[x].size();++i)
if (v[L2[x][i]] == 0)
DFS2(L2[x][i]);
vec[nr].push_back(x);
}
int main()
{
int N,M;
in >> N >> M;
for (int i = 1;i <= M;++i)
{
int x, y;
in >> x >> y;
L1[x].push_back(y);
L2[y].push_back(x);
}
for (int i = 1;i <= N;++i)
{
if (v[i] == 0)
DFS1(i);
}
v.reset();
for (int i = N-1;i >=0;--i)
{
if (v[s[i]] == 0)
{
++nr;
DFS2(s[i]);
}
}
out << nr << '\n';
for (int i = 1;i <= nr;++i)
{
for (int j = 0;j < vec[i].size();++j)
out << vec[i][j] << " ";
out << '\n';
}
return 0;
}