Pagini recente » Cod sursa (job #2248895) | Cod sursa (job #1382855) | Cod sursa (job #3225726) | Cod sursa (job #3039398) | Cod sursa (job #2723024)
#include <stdio.h>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
FILE *fin = fopen("ctc.in", "r");
FILE *fout = fopen("ctc.out", "w");
int n,i,j,x,y,nrcomp,nod,m;
bool viz[NMAX];
vector <int> graf[NMAX],invers[NMAX],comp[NMAX];
stack <int> st;
void dfs(int x)
{
int i;
viz[x] = true;
if(!graf[x].empty())
for(i=0; i<=graf[x].size()-1; ++i)
if(!viz[graf[x][i]])
dfs(graf[x][i]);
st.push(x);
}
void dfsinv(int x)
{
int i;
viz[x] = true;
if(!invers[x].empty())
for(i=0; i<=invers[x].size()-1; ++i)
if(!viz[invers[x][i]])
dfsinv(invers[x][i]);
comp[nrcomp].push_back(x);
}
int main()
{
fscanf(fin, "%d%d", &n,&m);
for(i=1; i<=m; ++i)
{
fscanf(fin, "%d%d", &x,&y);
graf[x].push_back(y);
invers[y].push_back(x);
}
for(i=1; i<=n; ++i)
if(!graf[i].empty() and !viz[i])
dfs(i);
for(i=1; i<=n; ++i)
viz[i] = false;
while(!st.empty())
{
nod = st.top();
if(!viz[nod])
{
++nrcomp;
dfsinv(nod);
}
st.pop();
}
fprintf(fout, "%d\n", nrcomp);
for(i=1; i<=nrcomp; ++i)
{
for(j=0; j<=comp[i].size()-1; ++j)
fprintf(fout, "%d ", comp[i][j]);
fprintf(fout, "\n");
}
//mama are mere
fclose(fin);
fclose(fout);
return 0;
}