Pagini recente » Cod sursa (job #2652002) | Cod sursa (job #890130) | Cod sursa (job #1986159) | Cod sursa (job #1087427) | Cod sursa (job #581020)
Cod sursa(job #581020)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100001;
int n;
int pos;
int cCount;
int ord[N];
bool vis[N];
vector <int> g[N];
vector <int> r[N];
vector <int> c[N];
void Read()
{
int m;
in >> n >> m;
while (m--)
{
int a, b;
in >> a >> b;
g[a].push_back(b);
r[b].push_back(a);
}
}
void DiggIn(int node)
{
vis[node] = true;
for (int i = 0; i < g[node].size(); ++i)
if (!vis[g[node][i]])
DiggIn(g[node][i]);
ord[++pos] = node;
}
void GetOrder()
{
for (int i = 1; i <= n; ++i)
if(!vis[i])
DiggIn(i);
}
void Add(int node, int comp)
{
vis[node] = false;
c[comp].push_back(node);
for (int i = 0; i < r[node].size(); ++i)
if (vis[r[node][i]])
Add(r[node][i], comp);
}
void GetComps()
{
for (int i = 1; i <= n; ++i)
if (vis[ord[i]])
Add(ord[i], ++cCount);
}
void PrintComps()
{
out << cCount << "\n";
for (int i = 1; i <= cCount; ++i)
{
for (int j = 0; j < c[i].size(); ++j)
out << c[i][j] << " ";
out << "\n";
}
}
int main()
{
Read();
GetOrder();
GetComps();
PrintComps();
return 0;
}