Pagini recente » Cod sursa (job #915840) | Cod sursa (job #2581753) | Cod sursa (job #116548) | Cod sursa (job #125948) | Cod sursa (job #2968864)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
const int N = 1e5;
vector <int> a[2 * N + 1], v[2 * N + 1];
int fre1[N + 1], fre2[N + 1], ctc[N + 1];
void dfs1(int x)
{
fre1[x] = 1;
for(auto vecin:a[x])
{
if(!fre1[vecin])
{
fre1[vecin] = 1;
dfs1(vecin);
}
}
}
void dfs2(int x)
{
fre2[x] = 1;
for(auto vecin:v[x])
{
if(!fre2[vecin])
{
fre2[vecin] = 1;
dfs2(vecin);
}
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
a[x].push_back(y);
v[y].push_back(x);
}
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(!ctc[i])
{
dfs1(i);
dfs2(i);
cnt++;
for(int j = 1; j <= n; j++)
{
if(fre1[j] && fre2[j])
ctc[j] = cnt;
}
memset(fre1, 0, sizeof(fre1));
memset(fre2, 0, sizeof(fre2));
}
}
out << cnt << '\n';
for(int i = 1; i <= cnt; i++)
{
for(int j = 1; j <= n; j++)
{
if(ctc[j] == i)
out << j << ' ';
}
out << '\n';
}
return 0;
}