Pagini recente » Cod sursa (job #253834) | Cod sursa (job #2859623) | Cod sursa (job #239481) | Cod sursa (job #2989479) | Cod sursa (job #1911298)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
FILE *fin = fopen("ctc.in", "r");
FILE *fout = fopen("ctc.out", "w");
vector <int> muchied[100001];
vector <int> muchiei[100001];
vector<int> componenta[100001];
stack <int> stiva;
char mark[100001];
char introdus[100001];
void dfs (int nod)
{
mark[nod]=1;
for(auto node : muchied[nod])
{
if(mark[node] == 0)
{
dfs(node);
}
}
stiva.push(nod);
}
void ctc(int x, int y)
{
if(introdus[x]==0)
{
introdus[x]=1;
componenta[y].push_back(x);
for(auto node : muchiei[x])
{
ctc(node,y);
}
}
}
int main()
{
int n,m;
fscanf(fin, "%d%d", &n, &m);
for(int i=1;i<=m;i++)
{
int x,y;
fscanf(fin, "%d%d", &x, &y);
muchied[x].push_back(y);
muchiei[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(mark[i]==0) dfs(i);
}
while(!stiva.empty())
{
int nod = stiva.top();
stiva.pop();
ctc(nod,nod);
}
int nrcomp = 0;
for(int i=1;i<=n;i++)
{
if(!componenta[i].empty())
{
nrcomp ++;
}
}
fprintf(fout, "%d\n", nrcomp);
for(int i=1;i<=n;i++)
{
if(!componenta[i].empty())
{
for(auto node : componenta[i]) fprintf(fout, "%d ", node);
fprintf(fout, "\n");
}
}
return 0;
}