Pagini recente » Cod sursa (job #752087) | Cod sursa (job #1790060) | Cod sursa (job #2976928) | nxdtjsyksrjs | Cod sursa (job #2806124)
#include <cstdio>
#include <vector>
#define N 100002
#include <deque>
using namespace std;
FILE* f, * g;
vector <int> graph[N], grapht[N], ctc[N];
int sol;
int elms[N];
bool viz[N];
void dfs(int nod)
{
viz[nod] = 1;
for (int i = 0;i < grapht[nod].size();++i)
if (!viz[grapht[nod][i]])
dfs(grapht[nod][i]);
ctc[sol].push_back(nod);
}
void topo(int nod)
{
viz[nod] = 1;
for (int i = 0;i < graph[nod].size();++i)
if (!viz[graph[nod][i]])
topo(graph[nod][i]);
elms[++elms[0]] = nod;
}
int main()
{
f = fopen("ctc.in", "r");
g = fopen("ctc.out", "w");
int n, m;
fscanf(f, "%d %d", &n, &m);
int x, y;
for (int i = 1;i <= m;++i)
{
fscanf(f, "%d %d", &x, &y);
graph[x].push_back(y);
grapht[y].push_back(x);
}
for (int i = 1;i <= n;++i)
if (!viz[i])
topo(i);
for (int i = 1;i <= n;++i)
viz[i] = 0;
for (int i = elms[0];i >= 1;--i)
if (!viz[elms[i]])
++sol, dfs(elms[i]);
fprintf(g, "%d\n", sol);
for (int i = 1;i <= sol;++i)
{
for (int j = 0;j < ctc[i].size();++j)
fprintf(g, "%d ", ctc[i][j]);
fprintf(g, "\n");
}
fclose(f);
fclose(g);
return 0;
}