Pagini recente » Cod sursa (job #2761104) | Cod sursa (job #522548) | Cod sursa (job #1492927) | Cod sursa (job #1822692) | Cod sursa (job #2562754)
#include <bits/stdc++.h>
#define nmax 100005
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, indexat, depth[nmax], st[nmax], ss, numscc;
vector <int> graph[nmax];
vector <int> ctc[nmax];
bitset <nmax> vizat;
int strongcon(int v, int indexat)
{
depth[v] = indexat;
st[ss++] = v;
vizat[v] = 1;
unsigned i, len;
len = graph[v].size();
int vecin;
for(i = 0; i < len; i++)
{
vecin = graph[v][i];
if(depth[vecin] == 0)
depth[v] = min(depth[v], strongcon(vecin, indexat + 1));
else if(vizat[vecin])
depth[v] = min(depth[v], depth[vecin]);
}
if(depth[v] == indexat)
{
do{
vecin = st[--ss];
vizat[vecin] = false;
ctc[numscc].pb(vecin);
}while(vecin != v);
numscc++;
}
return depth[v];
}
int main()
{
int i, x, y;
fin >> n >> m;
for(i = 0; i < m; i++)
fin >> x >> y, graph[x].pb(y);
for(i = 1; i <= n; i++)
if(depth[i] == 0)
strongcon(i, 1);
fout << numscc << '\n';
for(i = 0; i < numscc; i++)
{
x = ctc[i].size();
for(y = x - 1; y >= 0; y--)
fout << ctc[i][y] << ' ';
fout << '\n';
}
return 0;
}