Pagini recente » Cod sursa (job #1984654) | Cod sursa (job #2877518) | Cod sursa (job #540363) | Cod sursa (job #2410884) | Cod sursa (job #2806125)
#include <stdio.h>
#include <deque>
#include <bitset>
#include <cstring>
#include <vector>
using namespace std;
FILE* f, * g;
int start1[100002], start2[100002];///dimensiunea=nr de noduri;
int t1[3][400002], t2[3][400002];///dimensiunea 2*nr de muchii
int succesor[100002], predecesor[100002], tot;
deque <int> q;
bitset <100002> viz1;
bitset <100002> viz2;
vector <int> vecini[100002];
void dfs1(int nod)
{
int no;
viz1[nod] = 1;
no = start1[nod];
while (no)
{
if (!viz1[t1[0][no]])
dfs1(t1[0][no]);
no = t1[1][no];
}
q.push_back(nod);
}
void dfs2(int nod)
{
int no;
viz2[nod] = 1;
no = start2[nod];
while (no)
{
if (!viz2[t2[0][no]])
dfs2(t2[0][no]);
no = t2[1][no];
}
vecini[tot].push_back(nod);
}
int main()
{
int n, m, i, j, k1 = 0, o, cont, k2 = 0;
f = fopen("ctc.in", "r");
g = fopen("ctc.out", "w");
fscanf(f, "%d %d", &n, &m);
for (o = 1;o <= m;++o)
{
fscanf(f, "%d %d", &i, &j);
++k1;
t1[0][k1] = j, t1[1][k1] = start1[i], start1[i] = k1;
++k2;
t2[0][k2] = i, t2[1][k2] = start2[j], start2[j] = k2;
}
for (i = 1;i <= n;++i)
if (!viz1[i])
dfs1(i);
/*while(!q.empty())
{
x=q.front();
fprintf(g,"%d ",x);
q.pop_front();
}*/
int x;
while (!q.empty())
{
x = q.back();
q.pop_back();
if (!viz2[x])
dfs2(x), ++tot;
}
fprintf(g, "%d\n", tot);
for (i = 0;i < tot;++i)
{
for (j = 0;j < vecini[i].size();++j)
fprintf(g, "%d ", vecini[i][j]);
fprintf(g, "\n");
}
fclose(f);
fclose(g);
return 0;
}