Pagini recente » Monitorul de evaluare | Clasament blat6 | Cod sursa (job #1791799) | Cod sursa (job #3207072) | Cod sursa (job #952476)
Cod sursa(job #952476)
#include <stdio.h>
#include <stack>
#include <vector>
using namespace std;
vector<int> graf[100001],graft[100001];
int viz[100001],N,M;
stack<int> stiva;
vector<int> componenta;
vector< vector<int> > sol;
void citire()
{
FILE*f = fopen("ctc.in","r");
fscanf(f,"%d%d",&N,&M);
int x,y;
while(M != 0)
{
M--;
fscanf(f,"%d%d",&x,&y);
graf[x].push_back(y);
graft[y].push_back(x);
}
fclose(f);
}
void df1(int node)
{
viz[node] = 1;
for(vector<int>::iterator it = graf[node].begin(); it != graf[node].end(); it++)
if(viz[*it] == 0)
df1(*it);
stiva.push(node);
}
void df2(int node)
{
viz[node] = -1;
for(vector<int>::iterator it = graft[node].begin(); it != graft[node].end(); it++)
if(viz[*it] != -1)
df2(*it);
componenta.push_back(node);
}
void algraf()
{
for(int i = 1; i <= N; ++i)
if(!viz[i])
df1(i);
int elem;
while(!stiva.empty())
{
elem = stiva.top();
stiva.pop();
if(viz[elem] != -1)
{
df2(elem);
sol.push_back(componenta);
componenta.clear();
}
}
}
void afisare()
{
FILE*graf = fopen("ctc.out","w");
fprintf(graf,"%d\n", sol.size());
for(int i = 0, size = sol.size() ; i < size ; ++i)
{
for(vector< int >::iterator it = sol[i].begin(); it != sol[i].end(); it++)
fprintf(graf,"%d ", *it);
fprintf(graf,"\n");
}
fclose(graf);
}
int main()
{
citire();
algraf();
afisare();
return 0;
}